Programming

Binary Search

To search a billion records, a linear scan must traverse the continent of data footprint by footprint. Binary search cuts the entire continent in half thirty times. In thirty questions, a search space larger than humanity collapses to a single atom.

Scan 10^18 records for 31.7 years, or split the sorted horizon in 60 comparisons flat.

Mission 02about 8 min

Contract an interval of doubt across sorted data until sixty comparisons collapse a billion billion records to one.

  1. Bisect the search space and observe interval boundaries jump
  2. Trace the comparison decision tree down to its optimal leaves
  3. Inspect the mid-calculation overflow that broke Bentley and Bloch

After thisYou can replace linear scans with logarithmic boundary searches across any monotone predicate.

Short on timeThe RecursionTree panel in §4

Thirty questions to locate an atom

3 minthe hook

In 1986, Jon Bentley challenged professional programmers at Bell Labs and IBM to write binary search. Over ninety percent introduced off-by-one errors or infinite loops, despite having hours to test their work. The algorithm requires scarcely twenty lines of code, yet its precision punishes the slightest careless assumption.

At records, a scan from the left costs 31.7 years at its worst. The average is 15.8 years. Halving the interval needs 60 comparisons.

Eight sorted numbers sit in a row: [3, 9, 14, 21, 27, 33, 41, 58]. You want the 27.

Inspect index 3, see 21, and extinguish every index at or below 3 because sortedness forbids them from equaling 27. Inspect index 5, see 33, and the entire upper bracket vanishes. In two comparisons, seven candidates evaporate, leaving index 4 as the 27.

A sorted database holds 1,000,000,000 records. A linear search takes up to 1,000,000,000 comparisons. What is the absolute worst-case comparison count for binary search?

NextWhy does probing the physical middle fail without a monotonic invariant?

The illusion of looking at the middle

2 minthe trap

The standard operational framing is familiar: look at the midpoint, compare values, branch left or right, and repeat. That recipe tells you what to type, but obscures why the process runs so fast.

A naive linear search tests elements sequentially, spending up to comparisons. The fundamental question is not which element to inspect next. The true question is how much doubt a single comparison can extinguish.

NextHow does halving the interval contract the horizon of doubt?

The invariant: contracting the horizon of doubt

2 minthe invariant

The active state of binary search is an interval of surviving candidate indices, . Outside this bracket, every index has been mathematically proven impossible:

Sortedness is the contract that legitimizes mass elimination. If , then transitivity guarantees that for every , allowing one comparison to discard an entire prefix.

The midpoint is merely the optimal halving point. What the algorithm maintains is an interval guaranteed to preserve the answer, while halving its length at every step.

What happens if you run binary search for the number 3 on the unsorted array [9, 2, 8, 3, 7]?

NextWhat exact arithmetic prevents the recurrence from stalling?

The exact arithmetic of thirty questions

2 minthe algebra

A probe costs one comparison and leaves a subproblem at most half as large:

For powers of two, , the recurrence unrolls into a pure count of halvings:

Inverting back to yields an exact algebraic identity:

This matches the balanced master theorem case with , , and , giving .

Why is this optimal? Any comparison algorithm forms the decision tree: each internal node is a comparison, each leaf is a candidate, and two-way questions yield at most leaves. At its depth is 60.

An array of size has potential outcomes ( indices plus “absent”). To distinguish every outcome, the tree must have at least distinct leaves:

Binary search matches this information-theoretic lower bound exactly (Knuth 1973, §5.3.1).

nlog nnote
104ten cards
1007a hundred entries
1,00010a thousand entries
10⁶20a million
10⁹30a billion, in thirty comparisons
10¹⁸60squaring n doubles log n
10⁸⁰266atoms in the observable universe

Multiplying candidate count by 10 adds only ~3.3 comparisons. Each doubling costs exactly one comparison.

Emphasised column: log n · highlighted row: n = 10⁹

Surviving candidates after k probes, n = 10⁹ — exact arithmetic, hand-computed

1e-11e01e11e21e31e41e51e61e71e81e90102030k = 30 reaches one candidateprobes kcandidates still possible
halving, n / 2^klinear scan, n − k

On a logarithmic scale, halving is a straight downward line, reaching 1 in 30 steps. A linear scan barely registers on this axis, discarding an imperceptible fraction of the data.

NextHow does git bisect map real-world regressions to monotone predicates?

Driving the recurrence: why halving alone is not enough

2 minthe simulation

The recurrence panel sets , , : one child branch of half the size, plus one comparison per step.

T(n) = 1·T(n/2) + n0 — one comparison, then one half

k=0k=1k=2k=3k=4
k=0
1 nodes × 1 = 1
k=1
1 nodes × 1 = 1
k=2
1 nodes × 1 = 1
k=3
1 nodes × 1 = 1
k=4
1 nodes × 1 = 1

Geometric sum: Σk=0…4 ak·(n/bk)d = nd · Σ rk = nd·(L+1) = 1 · 5 = 5 (closed form 5)

n = bL = 16, L = 4, logb a = 0, d = 0, r = a/bd = 1. Every level ties at the top.

Balanced: T(n) = Θ(n^d · log n)

log_b a = d = 0. r = a/b^d = 1 exactly, so every level costs the same n^d = 1, and there are 5 such levels. No level dominates — they are tied.

  • logb a > d — leaf-dominated, T(n) = Θ(nlogb a)
  • logb a = d — balanced, T(n) = Θ(nd log n)
  • logb a < d — root-dominated, T(n) = Θ(nd)

Every level costs n⁰ = 1. The total work across L + 1 levels is simply L + 1, yielding Θ(log n).

Level holds a single node of size , spending work. Every bar on the ribbon has equal width 1, summing across levels to . Watch the ribbon: it is flat at one comparison per level, so the cost is the depth of the tree, not the number of leaves.

Now adjust the branching slider to .

1 minboss round

Suppose you modify binary search to explore both halves whenever you are unsure (a=2, b=2, d=0). Does halving the problem size preserve logarithmic time?

When , work doubles at each depth, and the tree becomes leaf-dominated at . The logarithm is not bought by halving the array. It is bought by : the merciless elimination of the unchosen half.

NextWhy did the middle-index calculation hide an overflow bug in Java for nine years?

Monotone predicates: from git bisect to root finding

2 minsystems

Binary search generalizes far beyond sorted arrays. It applies to any monotone boolean predicate that transitions from false to true:

  • git bisect. Finds the exact regression commit by treating “does the bug reproduce here?” as a monotone predicate over chronological history.
  • Root finding by bisection. Finds where a continuous function crosses zero by checking , halving the bracket interval each step.
  • Binary lifting. Finds lowest common ancestors in trees in by querying ancestor powers of two.

Breaking the comparison model breaks the logarithmic barrier. Interpolation search achieves on uniform keys, while hash tables achieve by forfeiting ordering entirely.

NextWhat structural invariant governs the next chapter?

The integer overflow bug that survived nine years in Java

2 minfrontier

Computing the midpoint as mid = (lo + hi) / 2 contains a subtle flaw. When exceeds , 32-bit signed integer addition overflows into negative numbers, causing array index out-of-bounds exceptions.

This bug persisted unnoticed inside Java’s java.util.Arrays.binarySearch for over nine years (Bloch 2006). The bug-free formulation is mid = lo + (hi - lo) / 2 or (lo + hi) >>> 1.

Precision in endpoint updates is essential. An incorrect endpoint update either enters an infinite loop or skips the target entirely.

Next missionBreadth-First SearchDFS circles the rim in 4 hops; expand in concentric ripples to hit the 3-hop chord.

Historical provenance and attributions

  • Knuth 1973 — The Art of Computer Programming, Vol. 3, §5.3.1: definitive analysis of binary search and the information-theoretic lower bound .
  • Bentley 1986 — Programming Pearls: highlighted the notorious implementation pitfalls of binary search among experienced software engineers.
  • Bentley, Haken, and Saxe 1980 — Formulation of the master theorem characterizing the balanced case.
  • Peterson 1957 — Introduced interpolation search, establishing average-case lookup on uniform keys.
  • Bloch 2006 — Identified and documented the nine-year-old integer overflow bug in Java’s standard library.