Binary Search: One Template for Every Variant

In Programming Pearls, Jon Bentley describes an experiment he ran for years on professional programmers, in courses at Bell Labs and IBM. He explained an algorithm every one of them already knew, gave them a couple of hours and the language of their choice, and asked them to implement it. Roughly 90% produced code with bugs. The algorithm was binary search: a dozen lines, taught in every introductory course on earth.

The history is worse than the classroom. The first binary search was published in 1946. The first version that worked correctly for arrays of every size appeared in 1962. The field needed sixteen years to get twelve lines right, and as we'll see shortly, it still wasn't done.

The last lesson ended on the question this algorithm answers. The converging pair retired one element per comparison; binary search retires half of everything that remains. It is the log n rung from lesson 1's ladder finally cashed in, and it is invariant-thinking, lesson 7's "find the reason a pointer never moves backward", at its absolute purest. This lesson does three things: watch the move earn its fame, watch exactly how it breaks, and then install the one template that dodges every trap and hands you every variant for free.

The move

Sixteen sorted numbers, target 53:

[ 2, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 ]

Probe the middle: index 7, value 23. Too small, and because the array is sorted, that single comparison says something enormous: 53 cannot be at this slot or anywhere left of it, because everything there is smaller still. Discard the middle and the entire left half. One comparison, eight survivors. Probe the middle of the survivors: 41, too small, four left. Probe: 47, too small, two left. Probe: 53. Found, in four comparisons.

Sixteen, to eight, to four, to two, to found. Now scale it. A thousand elements: ten probes. A million: twenty. A billion: thirty. Lesson 1 promised that whenever an algorithm halves its problem each step, the price tag reads O(log n), growth so slow it barely registers as growth. This is the purchase. Thirty comparisons against a billion elements is not an optimization; it's a different universe of cost, and the entire price of admission is one word: sorted.

Why discarding half is legal

Hold the discard up against lesson 7's vocabulary, because it is the same argument at a different scale. The converging pair retired one element per comparison, and the license was sortedness: if the smallest plus the largest is too small, the smallest fails with everyone. Same license here, bigger purchase: the middle element is too small, so everything left of it, smaller still, fails too. One comparison, half the search space proven irrelevant. Not skipped: proven, with a one-line proof attached to every discarded element.

And notice what the proof actually needed. Not sortedness itself, but a consequence of it: the answer to the question "is the value here at least 53?" reads, across the array, as a block of no's followed by a block of yes's. No, no, no, ..., yes, yes, yes. One flip, and it never flips back. A question with that shape is called a monotone predicate, and any monotone predicate supports the halving move, whether or not there's an array underneath. File that away; it is the key to the second half of this lesson and to most of what binary search does in production.

The bug that slept in the JDK for nine years

Now the infamy. In 2006, Joshua Bloch, who wrote much of Java's collections framework, published a Google blog post titled "Nearly All Binary Searches and Mergesorts are Broken". He wasn't exaggerating for effect. The binary search in java.util.Arrays, code he had written himself, had been wrong for nine years. The line:

int mid = (lo + hi) / 2;

Looks perfect. Walk the numbers. A Java int is 32 bits; the largest value it holds is 2,147,483,647. Binary search a sorted array of 1.5 billion elements, and eventually lo is around 1,000,000,000 and hi around 1,500,000,000. Their sum is 2,500,000,000, which does not fit. In 32-bit two's complement arithmetic the sum wraps around to -1,794,967,296, the division by two yields -897,483,648, and the search throws an ArrayIndexOutOfBoundsException reaching for a negative index.

Why did it take nine years to surface? Because the bug only triggers on arrays of more than about a billion elements, and for most of those nine years nobody had one. Memory grew, datasets grew, and one day someone's working program crashed on code "proven correct". And the provenance is the best part: Bloch had adapted the algorithm from Programming Pearls, where Bentley presents it alongside a proof of correctness. The proof is fine. It's a proof about mathematical integers, and the machine has 32 bits. Lesson 1 priced steps and lesson 2 priced memory; this is the third lesson in honest pricing: your correctness proofs are only as good as the arithmetic they assume.

The fix is one transformation:

int mid = lo + (hi - lo) / 2;

Same value, but no intermediate result ever exceeds hi, so it cannot overflow. (Java's actual fix used the unsigned shift, (lo + hi) >>> 1, which reinterprets the wrapped sum as unsigned; same effect, one instruction.)

The trifecta, and a loop that never returns

The overflow is the famous bug. It is not the common one. The common ones live in three innocent decisions every hand-rolled binary search forces:

1. Loop condition: while lo <= hi or while lo < hi?
2. Going left: hi = mid or hi = mid - 1?
3. Going right: lo = mid or lo = mid + 1?

Three decisions, two options each, eight possible loops. A few combinations are correct, for some variant. The rest miss the answer by one slot, examine the same slot twice, or never terminate. And this is why Bentley's programmers failed: the right combination depends on which variant you're writing (exact find, first occurrence, last occurrence, insertion point), so people memorize one variant and improvise the others under pressure. Improvising boundary arithmetic is how you lose.

The worst of the eight deserves a full demonstration, because it doesn't crash and doesn't return a wrong answer. It just never comes back. The job: the last index holding a value at most 3, on a two-element array.

items = [3, 5]
lo = 0, hi = 1
while lo < hi:
    mid = (lo + hi) / 2          # integer division rounds DOWN
    if items[mid] <= 3: lo = mid       # mid might be the answer, keep it in play
    else:               hi = mid - 1

Run it. mid = (0 + 1) / 2 = 0, rounding down. items[0] is 3, which qualifies, so lo = mid = 0. Which is what lo already was. Loop again: same state, same probe, same branch, same assignment. Nothing moves, forever. No exception, no wrong result, just a core pinned at 100%.

The poison is the pairing: mid rounds down toward lo, and the branch lo = mid doesn't step past it. The moment the interval shrinks to two elements, mid lands on lo and progress stops. Every binary search you write carries a proof obligation most people have never heard stated: every pass through the loop must strictly shrink the interval.

The template: find the first yes

The way out starts with a reframe, not with code. Stop searching for a value. Search for a boundary.

Take any monotone predicate over the indices 0..n-1: a yes/no question whose answers read as no's followed by yes's. The job is now: return the first index where the answer is yes (and if every index says no, return n, meaning "no index qualifies").

function first_yes(n, predicate):
    lo = 0
    hi = n
    # invariant: every index < lo is a proven NO
    #            every index >= hi is a proven YES
    #            [lo, hi) is unexplored
    while lo < hi:
        mid = lo + (hi - lo) / 2        # rounds down; cannot overflow
        if predicate(mid): hi = mid       # first yes is at mid or left of it
        else:              lo = mid + 1   # first yes is strictly right of mid
    return lo

Two markers. Everything left of lo is proven no; everything from hi onward is proven yes; between them, unexplored. Initially lo = 0, hi = n: nothing is claimed, and the virtual index n plays the role of an honorary yes. Probe the middle of the unexplored zone, ask the question, and move exactly one marker. When the markers meet, the unexplored zone is empty and lo stands on the first yes.

Why it cannot break

Both proofs fit in a breath, which is the point.

Termination. When lo < hi, the probe satisfies lo <= mid < hi: rounding down keeps it below hi, and it can't be below lo. So hi = mid pulls hi strictly down, and lo = mid + 1 pushes lo strictly up. Every pass shrinks the interval by at least one, and a shrinking interval hits empty. The infinite loop above is structurally impossible here, because the template never writes lo = mid: the probe's down-rounding biases it toward lo, and the template always steps past a no.

Correctness. Each branch claims only what the comparison proved. A yes at mid means everything from mid rightward is yes (the predicate flips once and never back), so hi = mid keeps the invariant true. A no at mid means everything up to and including mid is no, so lo = mid + 1 stays honest. The invariant holds on entry, survives every pass, and when lo == hi it reads: all no before lo, all yes from lo onward. First yes: lo.

That's the proof 90% of Bentley's programmers needed and improvised instead. Internalize it once, and you never write a different binary search again. (You can write the loop recursively; nobody does in production, because the iterative version is three variables and no stack. Recursion gets its full due next lesson.)

Every variant is a predicate

The payoff for learning one shape: every classic variant is the same four lines with a different question.

Read the exact-find row again, because it inverts the textbook ordering: exact find, the variant everyone learns first, is the derived one. Run lower bound, then look at the slot it returns. And the count row is quietly powerful: two searches, no scanning, O(log n) even if x fills half the array.

The names in that table are not interview jargon; they're the standard library. C++ ships std::lower_bound, std::upper_bound, and std::equal_range (both bounds in one call). Go's sort.Search is the template verbatim: you hand it n and a predicate, it hands you the first yes. The variants were never separate algorithms. They were always one algorithm and a menu of predicates.

Binary search on the answer

Now the version that shows up in real engineering, where there is no array at all.

A shipping problem: six packages on a conveyor with weights [3, 2, 2, 4, 1, 4] must ship within 3 days, in order, and you want the minimum daily weight capacity that makes the deadline. The candidates are capacities from 4 (the heaviest single package; anything less can never ship it) up to 16 (the total; ships everything in one day). The question "can we make the deadline at capacity c?" is checked greedily: fill each day until the next package would overflow, then start a new day. And it's monotone: more capacity never hurts, so the answers read no, no, ..., yes, yes. That's the only license halving ever needed. Search [4, 16), with 16 as the known yes:

Answer: 6. Four probes across thirteen candidates, and the thing we searched was never stored anywhere. It was a question. This pattern, binary search on the answer, converts "find the minimum capacity / smallest count / lowest threshold such that X works" into the template plus a feasibility check, and it is everywhere once you see it: square roots to a precision, smallest batch size that meets a latency budget, cheapest machine type that survives the load test.

git bisect: the binary search you already run

You have probably run a binary search this month without writing one.

Somewhere in the last 4,000 commits, a bug crept in. The current build is broken; a release from two months ago is fine. Checking one commit means a checkout, a build, a test run: five minutes, say. A linear scan is two weeks of machine time. But "does the bug reproduce at this commit?" is a monotone predicate over history: commits before the breaking change say no, commits after it say yes, and it flips exactly once. So git bisect checks out the middle commit. Broken? The culprit is in the older half. Clean? The newer half. 4,096 commits, twelve checkouts, an hour instead of two weeks. And git bisect run ./test.sh automates the loop entirely: hand git the predicate as a script, go get coffee, come back to the exact commit that broke production.

The same shape runs all over infrastructure: find the smallest replica count that survives the load test, the highest request rate before p99 falls over, the autoscaling threshold worth paging about. Whenever the question is "find the threshold" and trying one candidate is expensive, you are holding a monotone predicate, and twelve tries beat four thousand.

The honest performance beat

Lesson 2 taught us to price the steps, not just count them, so price these.

Each probe of a large array is a jump: the first lands at the midpoint, the next a quarter of the array away, then an eighth. On a billion-int array (4GB) the first two dozen probes each land megabytes from the last, which means each one is a likely cache miss, a full ~100ns hallway trip, and the prefetcher is blind here: it cannot predict a pattern that depends on data it hasn't seen. There is a second toll stacked on top. The comparison at each probe is a 50/50 coin flip by design; maximizing information per probe is the same thing as making the branch maximally unpredictable, and an unpredictable branch costs a pipeline flush most probes.

The consequences, in order of importance:

• At large n, none of this matters. Thirty scattered probes, even all missing to RAM, cost a few microseconds; scanning 4GB costs hundreds of milliseconds. The growth ladder from lesson 1 is undefeated.
• At small n, all of it matters. Below a few dozen elements the entire array is a couple of cache lines, and a linear scan is sequential, prefetched, perfectly predicted, and vectorizable. The scan wins outright, which is why real libraries (and lesson 1's insertion-sort oddity) cut over to linear behavior at small sizes.
• On disk, the constant is unaffordable. Thirty dependent probes is fine at 100ns each and catastrophic at 100µs each (recall lesson 2's table: an SSD read is "over a day" on the human clock). So databases don't binary search giant sorted files; they fatten each node to thousands of keys, discarding 99.9% per read instead of 50%. That structure is the B-tree, and part two of this course, dsa-patterns, builds it.

The template, in real code

The videos stay in pseudocode; here is first_yes specialized to lower bound in the three languages this course carries, plus the search-on-answer example.

The TypeScript version is fully hand-rolled because JavaScript has no binary search in the standard library, a genuine gap.

function lowerBound(items: number[], x: number): number {
  let lo = 0
  let hi = items.length // [lo, hi): lo..hi-1 unexplored, hi means "all no"
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2)
    if (items[mid] >= x) hi = mid // mid is a yes: answer at mid or left
    else lo = mid + 1 // mid is a no: answer strictly right
  }
  return lo
}

func lowerBound(items []int, x int) int {
	lo, hi := 0, len(items)
	for lo < hi {
		mid := lo + (hi-lo)/2
		if items[mid] >= x {
			hi = mid // first yes is at mid or left of it
		} else {
			lo = mid + 1 // first yes is strictly right of mid
		}
	}
	return lo
}

int lower_bound_idx(const std::vector<int>& items, int x) {
    int lo = 0;
    int hi = static_cast<int>(items.size());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;   // never overflows: sum never formed
        if (items[mid] >= x) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

One JS-specific trap in the TypeScript version: plain (lo + hi) / 2 cannot overflow here because JS numbers are doubles, safe to 2^53. But the "optimized" idiom (lo + hi) >> 1 truncates to 32 bits first, which faithfully reintroduces Bloch's bug on huge typed arrays. The safe habit costs nothing; keep it.

You rarely need to write this in Go, because the standard library already speaks predicate: sort.Search(len(items), func(i int) bool { return items[i] >= x }) is this exact function, invariant and all, and slices.BinarySearchFunc wraps the exact-find variant on top of it. Go's API designers read the same history this lesson did.

In C++, practice is to call std::lower_bound(items.begin(), items.end(), x); the hand-rolled version is here so you can see it is the same four lines. All three implementations share the load-bearing details: the half-open [lo, hi) interval with hi starting at n, the overflow-proof midpoint, the hi = mid that keeps a yes in play, and the lo = mid + 1 that makes the infinite loop impossible. There is no eighth-combination guesswork left to do.

And binary search on the answer, the shipping problem from above, in Go:

func shipWithinDays(weights []int, days int) int {
	lo, hi := slices.Max(weights), 0
	for _, w := range weights {
		hi += w // total weight: ships in one day, a guaranteed yes
	}
	feasible := func(cap int) bool {
		d, load := 1, 0
		for _, w := range weights {
			if load+w > cap { // next package overflows the day
				d, load = d+1, 0
			}
			load += w
		}
		return d <= days
	}
	for lo < hi {
		mid := lo + (hi-lo)/2
		if feasible(mid) {
			hi = mid
		} else {
			lo = mid + 1
		}
	}
	return lo
}

Read it as two halves. The bottom half is lowerBound with the comparison swapped for a function call; not one character of the loop changed. The top half is the problem-specific part: the candidate range (heaviest package up to total weight) and the greedy feasibility check, one O(n) pass per probe. Total cost: O(n log(sum)), and the structure makes the correctness argument modular. The loop is correct by the template's proof; all you owe the new problem is that the predicate is monotone, and "more capacity never needs more days" is a one-sentence argument.

Module two, closed

That closes out "linear structures and their patterns". You can now build the dynamic array, the string, the linked list, the stack, and the queue from raw memory up, price every operation they offer, and swing the two patterns that make flat data fast: pointers that never look back, and a boundary you can halve your way to. That toolkit is most of what production code does all day.

And look once more at what binary search actually does, because there is an idea hiding in it. It takes a problem, shrinks it to a smaller copy of itself, and solves that. We wrote it as a loop, and for binary search a loop is the right call. But that instinct, solve the smaller version of the same problem and trust the answer, is one of the deepest ideas in computer science, and it has a name: recursion. Next lesson opens a new module with the machinery underneath it. Every function call you have ever made pushes a frame onto a stack, and once you can see that stack, recursion stops being magic and starts being bookkeeping. The call stack, made concrete.