Binary Search

Two ways to find a value in a sorted run of 32. A linear scan reads every index up to the one it wants; binary search reads one, throws away half the array, and repeats. Drag the slider to move the target and compare the counts:

Notice that the scan's cost is the target's own position — put it at index 31 and it spends 32 comparisons — while binary search never spends more than six, wherever the target sits. The saving is not that it is clever about where it looks. It is that every comparison it makes is worth an entire half of what is left.

Here is the same search with the array drawn as a staircase, because sorted is what a staircase looks like. The dashed line is the target's own height; the probe stands above it or below it, and that is the entire decision. Drag the handle along the axis, then step the amber slider one comparison at a time:

Notice what the bracket underneath is doing. It is the set of indices that could still hold the target, and it never loses one: at the top of every iteration, if the target is in the array at all, its index lies in [lo, hi]. Every branch preserves it — a[mid] < target means every index up to mid is too small, so lo = mid + 1 discards nothing that could have been the answer.

The invariant is also where the cost comes from. Deleting mid from a range of n leaves ⌊(n−1)/2⌋ on one side and ⌈(n−1)/2⌉ on the other, so the worst survivor is ⌊n/2⌋. Drag n and count the rungs:

Because the worst case obeys T(n) = 1 + T(⌊n/2⌋), the chain from n down to nothing has exactly ⌊log₂ n⌋ + 1 rungs — six for 32, seven for 64, eleven for 1,024. That is a counting argument, not an appeal to “it halves”: the recurrence bottoms out when the range is empty. Put n on an axis where every step multiplies it, and drag the handle to a billion:

The comparison count is a straight staircase on that axis — one more tread every time n doubles, twenty at a million and thirty at a billion — while what a scan would read is the whole number underneath it. Space is three indices — lo, mid, hi — whatever n is.

Binary search does not need a sorted array. It needs something weaker: the yes/no question it asks at mid must, once true, stay true for every index after it. Sortedness is only the commonest way to arrange that. Drag the target and watch the strip of answers below the array:

Notice that the strip is always F…FT…T and never F T F T — not for any target, including one past the end. That is the real precondition: the predicate is monotone, and the array's only job is to make it so. Everything else here is finding the boundary in that strip. lower_bound, upper_bound, “the smallest k that works” and “the rotation point” are one loop with four questions.

So what happens when the precondition fails? Not an exception. Below is a sorted array with one bar you can move; the search is looking for 41, which sits at index 10 the whole time. Raise a[9] until it goes past it:

Watch the readout as you cross 41. Below 33 the array is out of order and the search still returns the right index — which is why this bug ships: the test data probed a path where the disorder did not reach. Above 41 the same search returns −1 for a value that is in the array and raises nothing. It fails silently, and the stack trace you eventually get comes from somewhere else entirely.

Which is why the useful reading of the precondition is the predicate, not the array. Here is the same array rotated — sorted nowhere except inside two runs — and the question a[i] ≥ a[0] is still monotone. Turn the rotation and watch the first false:

Notice that the strip is T…TF…F — the mirror of the last one, and just as searchable. The first false is the minimum's index, which is what LC 153 and LC 33 ask for, and at zero rotation there is no false and the loop returns n. The array was never the precondition: constructing a predicate you can prove monotone is most of the work in every hard variant.

The first is arithmetic. lo and hi are valid indices, so each fits in an int — but their sum need not. Drag the length past 2³⁰ and watch the bar cross:

Watch what (lo + hi) / 2 returns past it. The sum wraps negative in 32-bit two's complement and the shift keeps it negative — at 2³¹ − 1 elements the midpoint comes back as −3. lo + (hi − lo) / 2 computes the same midpoint from a difference that cannot overflow. Not hypothetical: java.util.Arrays.binarySearch shipped it broken for nine years, and Bloch's 2006 write-up is why everyone writes the second. An int[] of 2³⁰ elements is 4 GiB — absurd in 1997, ordinary now.

The second decision is the interval convention. A closed range [lo, hi] says both ends are candidates; a half-open range [lo, hi) says hi is one past the end. Step the same first-true search under both and watch the two hi markers:

Notice where they sit. The closed hi always points at a cell; the half-open one points at the gap between cells, which addresses “one past the last index” without inventing an index. They end differently too: closed with lo = hi + 1, half-open with lo = hi, and in both the answer is lo. Mixing them is how while (lo <= hi) ends up paired with hi = mid.

Which is the bug that never terminates. Every branch has to shrink the live range strictly, and in a closed loop hi = mid does not when lo, hi and the probe are the same index. Step it with the safe rule, then switch to the broken one:

Watch the bracket after step four. With hi = mid − 1 the range empties and the loop ends; with hi = mid it sits on one candidate forever, and the readout counts the steps. In production that is not a crash but a pinned core and a request that never returns, which no test of a return value can catch. The same check catches the mirror of it, where the surviving branch is lo = mid and the midpoint rounds the wrong way:

With mid = lo + (hi − lo) / 2 the probe lands on lo as soon as hi is lo + 1, so lo = mid assigns lo to itself and the range stops shrinking. Rounding up is the whole fix. The check is mechanical: show each branch strictly shrinks the range, and try it at hi == lo + 1.

With the interval settled, the half-open version is six lines and has no ans variable to forget: lo and hi are the answer's own bracket, and when they meet, lo is the first index where the predicate is true. Step it, then switch the predicate from ≥ to >:

Notice that the switch changes nothing about the loop and everything about where lo settles. a[i] ≥ 8 stops at the first 8; a[i] > 8 stops past the last 8. Those are lower_bound and upper_bound, and “the last 8” is upper_bound − 1 — no separate rightmost search, and none of the ans = mid bookkeeping a closed interval needs.

Which makes counting free. The two boundaries bracket the whole run of equal values, so their difference is how many there are: two searches, no scan, O(log n) even when the run is the entire array. Move the target through the values, and then to one that is not there:

Because both bounds are insertion points rather than element positions, they are defined for an absent value too — and then they are equal, the bracket collapses to a line, and the count is zero. That is also the presence test: i = lower_bound(x); i < n && a[i] == x. Exact match is the special case; the boundary is the general one, and the one that composes. Move the two ends of a range and watch the count follow:

Notice that the low end and the high end now answer two different questions, and the count is nothing but their difference: upper_bound(hi) − lower_bound(lo), two searches and no scan, even when the range is the whole array. Push both ends past 20 and the bracket collapses to a line — an empty range counts zero rather than erroring, because insertion points are defined everywhere.

Koko has four piles of bananas — 3, 6, 7 and 11 — and eight hours before the guards return. At speed k a pile of p takes ⌈p/k⌉ hours, because she never starts a second pile within an hour. Drag the speed and count the bites:

Notice that the strip along the bottom is F…FT…T again. It has to be: eating faster never takes longer, so once a speed fits, every larger speed fits. That monotonicity — not sortedness, there is no sorted array anywhere here — is the entire precondition. The candidate answers run 1 … max(pile), and each predicate evaluation costs one pass over the piles, so the whole thing is O(piles · log max-pile).

So run the same half-open first-true loop over the speeds instead of over indices. The bracket is now a range of answers, and mid is a speed nobody has tried yet:

Watch the bracket close on 4 — four probes, against eleven candidate speeds a loop would have tried. That is the shape of an enormous class of problems: minimum ship capacity, minimum days, smallest divisor, and every “minimise the maximum” question. The search is never the hard part; finding the predicate and proving it monotone is, and when it is not monotone the loop still returns something — quietly, exactly as it did when the array was out of order.

The answer axis gives you one thing an array cannot: it does not have to be bounded. With no natural top, double a bound until the predicate turns true, then binary-search the interval you jumped over. Drag the answer and count both phases:

Because doubling overshoots by less than a factor of two, the search phase costs no more than the doubling did — about 2·log₂ a probes for an answer at a, with no upper bound assumed. That is exponential search: what std::equal_range does on a forward iterator, and what Timsort's galloping mode does when one run keeps winning.

Binary search's first probes are half the array apart, so each lands in its own 64-byte cache line; a scan reads sixteen int32s per line in address order, which the prefetcher hides completely. Drag n and count the amber lines against the lines a scan streams through:

Notice how the tail of the search crowds into one line: sixteen int32s fit in 64 bytes, so the last probes land in a line already in L1. The readout counts how many, and it varies — an unaligned range of fifteen still straddles two. At 1,024 values that is 10 probes over 6 lines; at 2²⁰, 19 over 16 — and most are misses the prefetcher cannot anticipate, because each address depends on a comparison that has not finished.

Put numbers on it. A scanned element is 0.25 ns — an AVX2 compare retires several per cycle at ~3.5 GHz — a binary-search probe 2.5 ns, being a data-dependent branch that mispredicts about half the time at ~15 cycles, a hash lookup a flat 12 ns, plus 2 ns of call overhead on the two that touch the array. Move n across the crossing:

Because the axis multiplies at every step, binary search's cost climbs one flat tread per doubling while the scan's rears up — and the hash's flat 12 ns is the only straight line on the plot. Read the winner off it: the scan holds to about 40 elements, and past that the hash is cheapest at every n the slider reaches — at 1,024 values 12 ns against the search's 30 and the scan's 258. On this model binary search never wins outright. You choose it for the questions the other two cannot answer:

Watch what happens at a value the array does not contain. The hash has nothing to return; the same lower_bound still names the predecessor, the successor and the insertion point, and at a value that is there it answers presence too. Order is what a hash throws away.

# first index where pred(i) holds, or n if none does
lo, hi = 0, n                      # half-open [lo, hi)
while lo < hi:
    mid = lo + (hi - lo) // 2      # cannot overflow
    if pred(mid):  hi = mid        # mid is still a candidate
    else:          lo = mid + 1    # mid is ruled out
return lo                          # == hi; n means "no true index"

Here it is running on sixteen cells with the boundary under your hand. The numbers above the cells are the order it probes them in. Drag the boundary through the middle, then push it to past the end and to index 0:

Notice that both ends still answer. lo is an insertion point, not an element, so n means “no true index” and 0 means “all of them” — which is why the loop needs no empty-input special case.

The loop never checks the one thing it depends on. Corrupt a single answer in the strip and it keeps running, keeps terminating, and keeps returning an index:

Notice that nothing goes wrong on the way. Every probe is in bounds, the range shrinks on every branch, and the answer is a legal index — just not the first true one, and at some flips it is right anyway. No assertion inside the loop can catch that: monotonicity belongs to the whole strip, and the loop sees ⌊log₂ n⌋ + 1 cells of it. The three bugs that survive review:

• (lo + hi) / 2 → lo + (hi − lo) / 2. Past 2³⁰ elements the first returns a negative index.
• while (lo <= hi) with hi = mid. Spins at lo == hi. Closed takes mid − 1.
• A predicate that is not monotone. No exception, no bad index — just an answer, sometimes the right one.