Binary Search Patterns

Binary search finds something in a sorted collection by repeatedly cutting the search space in half. You look at the middle element; because the data is sorted, that single comparison tells you which half the answer must be in, so you throw the other half away and repeat. Each step halves what's left, so a collection of a million elements is exhausted in about twenty steps. That is the power of $O(\log n)$: doubling the data adds just one step.

The elementary version, "is x in this sorted array, and where?", is only the warm-up. What interviewers are really probing is whether you can recognise the shape: any problem where a yes/no test flips from "no" to "yes" exactly once as you turn a dial can be solved by binary search, even when there is no array in sight. That second pattern, "binary search the answer", is what separates people who memorised the template from people who understand it.

Why it is O(log n)

Start with n candidates. After one comparison you have at most n/2, then n/4, and so on. You can halve n only about $\log_2 n$ times before nothing is left, so the number of steps is

$$\text{steps} \approx \log_2 n .$$

Here $n$ is the size of the search space and $\log_2 n$ is how many times you can divide it by two. For $n = 1{,}000{,}000$ that is about 20; for a billion, about 30. The invariant that makes it correct: the answer, if it exists, always lies between lo and hi. Every step shrinks that window without ever excluding the answer.

Worked example: find 11

Search for 11 in [1, 3, 5, 7, 9, 11, 13, 15] (indices 0–7).

• lo = 0, hi = 7, mid = 3, a[3] = 7. Target 11 > 7, so go right: lo = 4.
• lo = 4, hi = 7, mid = 5, a[5] = 11. Found at index 5.

Two comparisons for eight elements; a linear scan would have taken six. In code, note the mid formula that avoids integer overflow on huge indices:

def binary_search(a, target):     # O(log n)
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # avoids lo+hi overflow
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

The pattern that matters: binary-search the answer

Many "minimize the maximum" or "find the smallest feasible X" problems have no explicit sorted array, but they hide one. If a value X is feasible and every larger value is also feasible (a monotone predicate: no, no, …, yes, yes), then binary-search over the range of X for the first "yes". Examples: the minimum ship capacity to deliver all packages within D days; the slowest eating speed Koko can finish the bananas in time; the square root of a number to a tolerance. You are searching the answer space, not a data array.

def first_true(lo, hi, feasible):   # smallest x in [lo, hi] with feasible(x)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid                 # mid might be the answer, keep it
        else:
            lo = mid + 1             # mid too small, discard it
    return lo

This exact bisection is how a pricing engine backs out Implied Volatility: option price rises monotonically with volatility, so to find the volatility that reproduces a market price you binary-search the volatility until the model price matches. Same $O(\log n)$ idea, applied to a continuous parameter instead of an array index.

The traps

• Off-by-one and infinite loops. Decide your invariant first: while lo <= hi with mid ± 1 for exact-match search, or while lo < hi with hi = mid for boundary/lower-bound search. Mixing them causes loops that never terminate.
• Rounding direction. In a while lo < hi loop, mid = lo + (hi - lo) // 2 rounds down; if your update is lo = mid (not mid + 1) you can get stuck. Match the rounding to the update.
• Overflow. (lo + hi) / 2 can overflow in fixed-width integer languages; lo + (hi - lo) / 2 never does. A famous bug that sat in production libraries for years.
• Precondition. The data (or the predicate) must actually be monotone. Binary search on unsorted data returns confident nonsense.

In quant-dev interviews binary search shows up as search-in-rotated-array, find-peak-element, kth-smallest, median-of-two-sorted-arrays, and the whole "binary-search-the-answer" family. On the desk the same bisection roots out implied volatility, yields from bond prices, and any quantity defined only implicitly by a monotone equation.