Binary search, step through it on a sorted array

Think of looking up a word in a paper dictionary. You don’t read from the first page: you open it in the middle, see whether your word comes before or after, and repeat in the half that’s left. Binary search is that strategy made precise. It only works because the data is sorted, which is what lets one comparison rule out half the remaining candidates.

Step through it

The array below is searched for 63. lo and hi mark the range that could still contain the target; mid is the element being probed. Faded cells have been ruled out. Try a target that is not in the array, then switch to the lower-bound variant.

Why it is so fast

Each probe either finds the target or at least halves the number of candidates. Starting from $n$ candidates, after $k$ probes at most $n / 2^k$ remain, so the search ends after at most $\lfloor \log_2 n \rfloor + 1$ probes. That is $O(\log n)$ time, against $O(n)$ for scanning.

The catch is the precondition. Sorting costs $O(n \log n)$, so binary search pays off when you search the same data many times, or when it arrives sorted anyway.

Why it is correct

The loop maintains one invariant: if the target is anywhere in the array, it is in $A[lo..hi]$. It holds at the start, when the range is the whole array. Each probe keeps it: if $A[mid] < \text{target}$, then because the array is sorted, everything at or left of $mid$ is also too small, so moving $lo$ to $mid + 1$ loses nothing. The other case is symmetric.

The loop also terminates, because $hi - lo$ shrinks on every iteration. When the range is empty ($lo > hi$) the invariant says the target is nowhere, so “not found” is the right answer. Invariant plus termination is the standard way to prove a loop correct, and it is the loop version of proof by induction.

Where it goes wrong

Jon Bentley reported that when he asked professional programmers to write binary search, most of their versions had bugs. The usual suspects are:

• Mixing up the boundaries. Decide whether hi is inclusive (the last candidate) or exclusive (one past it) and stick to it. The classic version on this page is inclusive (while lo ≤ hi, hi ← mid − 1); the lower-bound version is exclusive (while lo < hi, hi ← mid). Mixing the two styles creates infinite loops or skipped elements.
• Not making progress. Writing lo ← mid in the inclusive version can loop forever when lo and hi are neighbours, because mid rounds down to lo.
• Overflow. In languages with fixed-size integers, (lo + hi) / 2 overflows when both are large. Writing lo + (hi − lo) / 2 avoids it. The JDK’s own binary search had exactly this bug until 2006.

Lower bound: the first position that is at least the target

Often you want more than “is it there?”: where is the first copy of a repeated value, or where would a new value be inserted to keep the array sorted? The lower-bound search answers both. It returns the smallest index $i$ with $A[i] \ge \text{target}$ (or $n$ if there is none). It never stops early, so it always uses about $\log_2 n$ probes, and it finds the leftmost of several equal values. Python’s bisect_left and C++’s std::lower_bound are this function.

Binary search on the answer

The idea works on any yes/no question whose answer flips exactly once as a number increases. To find the integer square root of $N$, the largest $x$ with $x^2 \le N$, search over $x$ instead of over an array: the test “$x^2 \le N$?” is true up to the answer and false after it.

References

1. D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, §6.2.1.
2. J. Bentley, Programming Pearls, 2nd ed., Addison-Wesley, 2000. Column 4 is about writing a correct binary search.
3. “Binary search”, Wikipedia.