Binary Search

How software finds one value among millions by throwing half the haystack away every single step.

Binary Search — interactive 3D animation

Step 01 of 07

1 · A sorted haystack

Sixteen values, strictly ascending, sitting in a row. That single property — sorted — is the whole trick: because every value bigger than X sits to its right and every value smaller sits to its left, we never have to check them one by one.

Step 02 of 07

2 · Low and high

Binary search tracks two bounds: lo starts at the first index, hi at the last. The target — if it exists in the array at all — is guaranteed to be somewhere between them. Every comparison that follows exists to move one of these two markers.

Step 03 of 07

3 · Probe 1 — check the middle

Jump straight to the midpoint, index 7, value 41. Comparing it to our target, 84: 41 is smaller, so the target — if present — must be to the right. Every value at index 7 and below, eight of the sixteen, is eliminated in this one comparison.

Step 04 of 07

4 · Probe 2 — halve again

lo jumps straight to 8 — no need to re-check anything we just discarded. New midpoint: index 11, value 65. Still smaller than 84, so the left half of what remains is thrown away too. Two comparisons in, and we have already ruled out twelve of the sixteen values.

Step 05 of 07

5 · Probe 3 — down to two

Midpoint 13, value 77 — still under 84. lo advances to 14. Only two tiles remain in play: index 14 and 15. Three comparisons have done the work that would have taken a plain left-to-right scan up to fourteen.

Step 06 of 07

6 · Probe 4 — found

Midpoint 14, value 84. A match. Sixteen values, four comparisons — exactly log2(16), the worst case this array size can ever demand. Scale the array up to a million entries and the worst case only grows to about twenty comparisons; a plain scan could need all million.

Step 07 of 07

7 · O(log n) — why it scales

Every extra comparison lets binary search discard HALF of whatever is left, not a fixed chunk — so the work needed grows logarithmically, not linearly, with the size of the data. At 4 billion sorted items (2^32), the worst case is still only 32 comparisons. This is the same idea behind `git bisect` hunting down which of thousands of commits broke a build.