Binary Search

Sorted data answers "is x here?" by discarding half of what is left at every step. Two million sorted record ids need at most 21 comparisons, where a scan needs up to two million, and doubling the data adds one comparison, not a second scan. Few ideas in this book buy so much for so little code.

The price is paid up front and in the details. The data has to be sorted and kept sorted, and the ten-line loop has three places to go wrong, one of which sat inside the Java standard library for nine years before anyone noticed.

Halving as a Counting Argument

Compare the target with the middle element of the range still in play. If the middle is smaller, the target can only be in the upper half; otherwise it can only be in the lower half. One comparison throws away half the remaining range, so k comparisons decide among 2 to the power k items.

Sixteen items need four comparisons, because 16 is 2 times 2 times 2 times 2. Two million need 21, because 2 to the 21st is 2,097,152, the first power of two above two million. A billion need 30. Every doubling of the data costs exactly one more comparison, which is what O(log n) means when it is written out: four million ids need 22.

The Invariant That Keeps It Correct

The loop stays correct only if it states what its window means, for example "if the target is present, it lies at or after lo and before hi", and keeps that statement true on every branch. Almost every broken binary search breaks at one of three places.

The first is a bound that is off by one, so the loop stops a step early and never examines the last element. The second is a midpoint that stops moving: when two items remain and the update sets the bound back to the midpoint instead of past it, the window never shrinks and the loop never ends. The third is arithmetic. Computing the midpoint as lo plus hi, divided by two, overflows a 32-bit integer once lo plus hi passes about 2.1 billion, which happens on arrays of over a billion elements. Joshua Bloch reported that bug in the JDK's binarySearch in a Google Research blog post of 2 June 2006, after it had lain in wait for nine years or so. Python's integers grow as needed and cannot overflow, as Chapter 2 explains, but the first two traps apply in every language.

def lower_bound(items, x):
    # invariant: items[:lo] < x  and  items[hi:] >= x
    lo, hi = 0, len(items)
    while lo < hi:
        mid = lo + (hi - lo) // 2      # never overflows, in any language
        if items[mid] < x:
            lo = mid + 1               # mid is too small: move past it
        else:
            hi = mid                   # mid may be the answer: keep it
    return lo

The function above keeps two promises: everything before lo is smaller than the target, and everything from hi onward is not. Each branch keeps both promises and shrinks the window by at least one, so the loop ends, and when it does lo and hi meet at the first position whose item is not smaller than the target. The midpoint is computed as lo plus half the distance to hi, which gives the same answer and never produces a sum larger than hi.

The Useful Question: Where Would x Go

"Is it present" is the weak form of the question. The strong form returns the first position whose item is not less than x, called the lower bound, and that one number answers far more. The target is present if the item at that position equals it. The number of copies of x is the upper bound, the first position past every x, minus the lower bound. Every id in a range lies between the lower bound of the start and the lower bound of the end. And the lower bound is where x would be inserted to keep the list sorted. Python's standard bisect module ships these two searches, as bisect_left and bisect_right.

Bisecting Anything That Flips Once

Binary search needs sorted answers, not a sorted array. Any yes-or-no question whose answer is "no" up to some point and "yes" after it can be halved the same way: the smallest buffer size that stops a video from dropping frames, the lowest timeout at which a flaky test passes, the first release that fails a test. None of these involves an array. Each needs only a way to ask the question at a chosen point.

Git's bisect command is this idea applied to a history of commits. Given one good commit and one bad one with a thousand commits between them, it tests the middle, keeps the half that contains the change, and finds the commit that broke the build in about 10 test runs, because 2 to the 10th is 1,024.

What Halving Costs on Real Memory

Twenty-one comparisons sounds like nothing, but the probes jump across the array. Two million 8-byte ids take 16 megabytes, larger than a typical L2 cache, so the first probes land far apart in memory: the first jumps 8 megabytes, the next 4, then 2. Each of those early probes is likely a cache miss at around 100 nanoseconds, from the ladder in Chapter 4. Only the last few land within one 64-byte cache line, which holds eight ids.

In a real search of the 2 million ids for record 1048576, 18 of the 21 probes touched a cache line the search had not touched before. So one lookup can cost around 18 misses, a couple of microseconds, where a hash lookup (Chapter 5) touches one or two lines. And below a few hundred items, a plain scan often wins outright: it reads contiguous memory at full speed, and its branch goes the same way every time, so the processor predicts it (Chapter 3), while every halving step is a coin flip the predictor cannot learn.

The Price of Keeping It Sorted

The 21 comparisons are bought twice. Once by sorting, which costs n log n (the next topics). And again on every insert, because inserting into a sorted array means shifting everything after the insertion point one place to the right. Measured on Python 3.15, inserting 100,000 random values one at a time into a sorted list took 0.5 seconds; 200,000 took 2 seconds, four times as long for twice the data. Sorting the same 200,000 values once took 0.03 seconds.

So a sorted array is for data that is read far more than it changes, rebuilt in bulk. Data that changes constantly wants the structures that keep binary search's cost while making inserts cheap: a balanced tree in memory or a B-tree on disk, both from Chapter 6.