Binary search: halve it until you find it

Think of a number between 1 and 1,000,000 and let a friend guess. If you only say "yes" or "no", they could need a million guesses. If you say "higher" or "lower", they need at most 20, because every answer throws away half of what is left: a million, half a million, a quarter million… down to one in about 20 halvings.

Binary search is that game played on a sorted array. It is how a dictionary lookup, a database index or git bisect finds things fast. The catch is the word sorted: the "higher or lower" answer only means something when the order is fixed.

The number of halvings it takes to shrink $n$ items to one is $\log_2 n$, so binary search needs at most $\lceil \log_2 (n+1) \rceil$ probes, against up to $n$ for checking every element.

lo and hi

The ends of the window: the positions that could still hold the target. Everything outside has been ruled out.

mid

The middle of the window, ⌊(lo + hi) / 2⌋. The only element the algorithm actually looks at each step.

probe

One comparison of A[mid] with the target. Counting probes is how we measure the work.

sorted order

The promise that makes the trick legal: everything left of mid is no bigger, everything right is no smaller.

Step forward with the arrow buttons (or click the visualiser and use ← →). Watch the shaded window: each probe throws away one half, and the narration says why that half cannot contain the target.

This time the player stops before every decision and asks what happens next. Decide from the values you can see, then step forward to check. Predicting before you watch is what turns watching into learning.

Try the inputs that sit at the edges: a target at the very first or last position, or one that isn't there at all. Count the probes each time and compare them with $\lceil \log_2 (n+1) \rceil$. Then type your own sorted values.

• Binary search keeps a window that must contain the target if it exists, and halves it with each probe.
• It needs about $\log_2 n$ probes: 20 for a million items.
• Every branch must remove mid, or the window can stop shrinking.
• It only works on sorted data. The same idea powers searching over answers too: whenever "too small / too big" is monotonic, you can binary search it.