Binary Search & Divide-and-Conquer Algorithms Flashcards

Question 1

What is the mandatory precondition for applying binary search?

Accepted Answer

The input sequence must be **monotonically ordered** (sorted in ascending or descending order). Without order, comparing against the midpoint provides zero information about which half contains the target.

Question 2

How is the midpoint computed to avoid 32-bit integer overflow?

Accepted Answer

$$	ext{mid} = 	ext{low} + \left\lfloor \frac{	ext{high} - 	ext{low}}{2} ightfloor$$

Evaluating `(low + high) / 2` risks integer overflow when `low + high > 2^{31} - 1` in fixed-width integer environments (e.g. C++, Java).

Question 3

What is the asymptotic time complexity of binary search?

Accepted Answer

- **Best Case**: $O(1)$ (target located at initial midpoint)
- **Average Case**: $O(\log n)$
- **Worst Case**: $O(\log n)$ (target at extreme ends or absent entirely)

Recurrence relation: $T(n) = T(n/2) + O(1)$.

Question 4

What are the pointer adjustment rules in canonical binary search?

Accepted Answer

While `low <= high`: - If `arr[mid] < target`: search upper half by setting `low = mid + 1` - If `arr[mid] > target`: search lower half by setting `high = mid - 1` - If `arr[mid] === target`: return index `mid` - If `low > high`: target is not present (return -1)

Question 5

What is the worst-case number of comparisons for an array of 1,024 elements?

Accepted Answer

**11 comparisons**.
Since $2^{10} = 1024$, binary search divides the search space in half at each iteration: $\lfloor \log_2 1024 \rfloor + 1 = 11$ comparisons.

Question 6

What is the auxiliary space complexity of iterative vs recursive binary search?

Accepted Answer

- **Iterative Binary Search**: **$O(1)$** auxiliary space (stores only pointers `low`, `high`, `mid`).
- **Recursive Binary Search**: **$O(\log n)$** auxiliary space due to call-stack frames.

Question 7

How does lower_bound search handle duplicate elements?

Accepted Answer

When `arr[mid] >= target`, it updates `high = mid` (or `high = mid - 1`) rather than halting, continuing to explore the left sub-array to guarantee finding the **first occurrence** of the target.

Question 8

How does binary search performance compare to linear search on 1,000,000 items?

Accepted Answer

- **Linear Search ($O(n)$)**: Up to 1,000,000 element comparisons.
- **Binary Search ($O(\log n)$)**: At most $\lceil \log_2 10^6 \rceil = 20$ comparisons.
Binary search is ~50,000× faster at this scale.

Question 9

Name three critical systems engineering applications of binary search.

Accepted Answer

1. **Database B-Trees**: Navigating keys within internal nodes.
2. **Git Bisect**: Pinpointing the regression-introducing commit in $O(\log n)$ repository checkouts.
3. **Network Routing**: Longest-prefix matching on sorted IP ranges.

Question 10

What is the termination condition when the target is absent from the array?

Accepted Answer

The loop terminates when **`low > high`**, indicating the active search interval $[	ext{low}, 	ext{high}]$ has shrunk to zero elements.

Binary Search & Divide-and-Conquer Algorithms

Add Card