Divide And Conquer – GATE CSE AlgorithmsPractice Questions & PYQs

Worst-case comparisons for binary search $= \lfloor \log_2 n \rfloor + 1 = \lfloor \log_2 15 \rfloor + 1 = 3 + 1 = \mathbf{4}$ comparisons. Trace: search space sizes are $15 \to 7 \to 3 \to 1 \to$ not found (4 comparisons). For $n = 15$, the worst case is an unsuccessful search or a search for an element at certain boundary positions.

While a Divide and Conquer approach can solve this in $O(n log n)$, the Boyer-Moore Voting Algorithm solves it in $O(n)$ time and $O(1)$ space.

Binary search halves the search space each time.

Worst case comparisons = ⌈log₂(1000)⌉ = ⌈9.97⌉ = 10.

Binary search requires O(1) random access, which only arrays provide. Linked lists lack efficient indexed access.

Binary search halves the problem each time ⇒ O(log n).

An element is found in exactly $k$ comparisons if it is not found in comparisons 1 through $k-1$ but found at comparison $k$. In the binary search tree representation, these are elements at depth $k-1$ (0-indexed depth). At depth $k-1$, there are $2^{k-1}$ nodes. Hence exactly $2^{k-1}$ elements require exactly $k$ comparisons to be found (for $k \geq 1$, assuming a full binary search tree).

The 'Median of Medians' algorithm is a deterministic divide and conquer approach that finds the $k^{th}$ smallest element (including the median) in $O(n)$ worst-case time.

Expanding the recurrence: $T(n) = log n + log(n-1) + dots + log 1 = log(n!)$. By Stirling's approximation, $log(n!) = Theta(n log n)$.

(A) TRUE: Binary search on the answer space $[0, n]$ to find $\sqrt{n}$ - each step halves the range. $O(\log(n/\epsilon))$ for precision $\epsilon$. (B) TRUE: Finding the first element $> k$ in a sorted array is the upper_bound operation - standard binary search variant in $O(\log n)$. (C) FALSE: Finding a peak element in an unsorted array requires $O(n)$ in general (though a unimodal array allows $O(\log n)$). (D) TRUE: Count of elements $< k$ = index of lower_bound($k$) - found in $O(\log n)$ via binary search.

(A) TRUE: Binary search on the answer space (capacity range) - check if a given capacity is feasible in $O(n)$; binary search finds minimum in $O(n \log n)$ total. (B) FALSE: Finding the $k$-th smallest in an unsorted array requires $O(n)$ via quickselect or $O(n \log n)$ via sorting - binary search is not directly applicable without sorting first. (C) TRUE: The bisection method is exactly binary search on a continuous domain - halve the interval at each step. (D) TRUE: The classical algorithm finds the median of two sorted arrays in $O(\log(\min(m,n)))$ using binary search on partition indices.

The best case for binary search occurs when the target element is exactly at the middle index on the first comparison. For $n = 7$ (1-indexed), $\text{mid} = \lfloor (1+7)/2 \rfloor = 4$. If $A[4]$ is the target, only $\mathbf{1}$ comparison is needed. This is the best case regardless of $n$ - finding the element at the first mid position always requires exactly 1 comparison.

Search for $6$ in $[1,3,5,7,9,11,13,15]$ (indices 0-7): Step 1: low=0, high=7, $\text{mid}=3$, $A[3]=7 > 6$, set high=2. Step 2: low=0, high=2, $\text{mid}=1$, $A[1]=3 < 6$, set low=2. Step 3: low=2, high=2, $\text{mid}=2$, $A[2]=5 < 6$, set low=3. Now low=3 $>$ high=2, exit. Wait - recalculating: Step 1: mid=3, $A[3]=7>6$, high=2. Step 2: low=0,high=2, mid=1, $A[1]=3<6$, low=2. Step 3: low=2,high=2, mid=2, $A[2]=5<6$, low=3. Low $>$ high - not found. Sequence of mid values: $3, 1, 2$.

a=3, b=3, log_b(a)=1. f(n)=n=Θ(n^1). Case 2 → T(n)=Θ(n log n). Note: log₃n and log₂n differ by constant factor.

$T(n) = T(n/2) + O(1)$ fits Master theorem with $a = 1$, $b = 2$, $f(n) = O(1)$. $n^{\log_b a} = n^{\log_2 1} = n^0 = 1 = \Theta(1) = \Theta(f(n))$. This is Case 2: $T(n) = \Theta(\log n)$. Alternatively, unrolling: $T(n) = T(n/2^k) + k \cdot O(1)$; when $n/2^k = 1$, $k = \log_2 n$, so $T(n) = O(\log n)$.

For $n = 8$ (complete binary search tree of height 3): elements at depth 0 (1 element): 1 comparison each → $1 \times 1 = 1$. Elements at depth 1 (2 elements): 2 comparisons each → $2 \times 2 = 4$. Elements at depth 2 (4 elements): 3 comparisons each → $4 \times 3 = 12$. Total $= 1 + 4 + 12 = \mathbf{17}$ comparisons. Average comparisons per element $= 17/8 \approx 2.125$.

When $\text{low}$ and $\text{high}$ are large integers (e.g., near $2^{31} - 1$ in a 32-bit system), $\text{low} + \text{high}$ can overflow the integer range, producing a negative or incorrect result. Using $\text{mid} = \text{low} + (\text{high} - \text{low}) / 2$ avoids overflow since $(\text{high} - \text{low})$ is always non-negative and at most $n-1$. This is a classic programming pitfall documented in binary search implementations.

Ternary search reduces the search space to $n/3$ each step - $O(\log_3 n)$ steps. However, each step requires 2 comparisons (compare with both $\text{mid1}$ and $\text{mid2}$). Total comparisons $\approx 2\log_3 n = 2 \cdot \frac{\log_2 n}{\log_2 3} \approx \frac{2}{1.585} \log_2 n \approx 1.26 \log_2 n$. Binary search uses 1 comparison per step: $\log_2 n$ total. Since $1.26 \log_2 n > \log_2 n$, ternary search performs more comparisons than binary search in the worst case.

Any comparison-based sorting algorithm can be represented as a decision tree. To distinguish between $n!$ permutations, the height of the tree must be at least $lceil log_2 (n!) ceil$.

An element requiring $\lfloor \log_2 n \rfloor + 1$ comparisons is one that lies at the deepest level of the binary search decision tree. This is the worst case - the element is found only after exhausting all possible halvings. Not all elements at the first or last position require this many comparisons (e.g., if $n = 7$, element at position 4 is found in 1 comparison). The deepest-level elements are those at leaf nodes of the binary search tree.