Halving the haystack

Why does throwing away half of what remains find one item among a billion in about thirty tries?

A billion sorted records, and you want one of them. Thirty probes will do it. Not thirty thousand, not thirty million — thirty, fewer than the number of pages you would flip idly through a magazine.

That number is so small it invites suspicion. Where does the work go? Nothing was skipped by luck, and no record was ignored — so what exactly happened to the other 999,999,999?

Start with what a single probe can tell you. You look at the middle record and compare it to your target. The answer is one of three things: smaller, larger, equal. Suppose it is smaller. What have you learned about the entire lower half?

Everything. Because the records are sorted, one comparison against the middle settles the fate of every record below it at once, without touching any of them. That is the whole trick, and it is worth pausing on: the work is not in the probe, it is in the sortedness that was established beforehand. The order is a debt already paid, and each probe collects on it.

So each step leaves you with half of what you had. Ask the question the other way around, which is where the arithmetic becomes easy: how many halvings does it take to shrink a billion to one? Equivalently, how many doublings take one up to a billion? Two doubled thirty times is 1,073,741,824 — just past a billion. So thirty. The count of probes is not proportional to the size of the pile; it is proportional to the number of digits in the size of the pile.

There is a second way to see the same number that I find more honest, because it says why no cleverer method could do much better. Each comparison returns one of a small fixed number of answers — call it one bit of information, roughly. To single out one item from a billion candidates you must distinguish a billion possibilities, and that takes about thirty bits, since 2^30 just exceeds a billion. Thirty yes-or-no answers is the minimum any question-asking procedure could need. Binary search is not merely fast; it is asking questions that each carry a full bit, and you cannot buy more than that per question.

Now, what would it cost to be careless? Notice what the procedure needs: it must be able to jump to the middle of the remaining region instantly. On an array that is arithmetic. On a linked list, reaching the middle means walking there, and the walking undoes everything — the same halving logic yields no saving at all. The magic is not the halving by itself; it is halving plus the ability to land anywhere in constant time.

And where does correctness live? In one sentence you should be able to state: the target, if present, is always inside the region still under consideration. Every probe preserves that. The region shrinks strictly each time, so the procedure must stop. Those two claims — the invariant and the shrinkage — are the entire proof, and they are also where implementations go wrong. The most famous case: computing the midpoint as the sum of the two endpoints divided by two overflows a fixed-width integer for large arrays. That bug sat in Java's library implementation and in the standard published description for years; Joshua Bloch wrote it up in 2006, and the fix is to compute low plus half the difference instead. A method with a two-line proof still shipped broken for two decades, which says something about how easy it is to believe you have understood it.

Two refinements worth making explicit.

First, "logarithmic" is not a synonym for "fast", it is a statement about how cost responds to growth. Doubling the data adds exactly one probe. That is why the number stays small at absurd scales: a trillion records costs forty. The interesting property is the flatness, not the smallness.

Second, the thirty probes are not free in wall-clock terms, and this is where the tidy model diverges from a real machine. Each probe lands in an unrelated part of memory, so nearly every one is a cache miss, and the branch it takes is unpredictable. A linear scan of a few dozen elements is often faster than three or four probes, which is why practical implementations stop halving below some threshold and scan. The model counts comparisons; hardware charges for memory traffic. Both are true, and confusing them is how people end up surprised that their asymptotically superior code lost a benchmark.

• Interpolation search, which guesses where in the range the target should fall and can beat halving on uniformly distributed keys — but degrades badly when the distribution is skewed.
• B-trees, which apply the same logic with a branching factor of hundreds so that each probe is one disk read.
• Binary search on an answer rather than an array: any monotone yes-or-no predicate can be halved the same way.

Every term the collection defines is gathered in the glossary.