Binary search, deeply

lesson 2-2 · ~14 min · 4/30

Binary search, deeply

If the list is sorted, you can do something drastic: check the middle element, and throw away half the list.

Middle value too small? The target can only be in the right half.
Middle value too big? It can only be in the left half.
Equal? Done.

Each check halves what remains: 1,000,000 → 500,000 → 250,000 → ... → 1. That takes about log₂(n) checks, so a million items need about 20, not a million. This is binary search, the single most-tested algorithm in interviews, and also the one with the most famous off-by-one bugs. We will write it slowly and correctly.

Binary search for 23: the gold range is what is still possible, and each middle check cuts it in half. Three checks instead of ten.

Code exercise · python

Run this. The print inside the loop traces exactly which index gets checked and how the [lo, hi] range shrinks. Match it against the figure above.

A full trace, by hand

Interviewers routinely ask you to trace binary search on paper, because the trace exposes whether you really know where lo, hi, and mid go. Searching for 23 in [4, 8, 15, 16, 23, 42, 77, 91] (indexes 0–7):

step	lo	hi	mid	nums[mid]	verdict
1	0	7	3	16	too small → lo = 4
2	4	7	5	42	too big → hi = 4
3	4	4	4	23	found

Three checks for eight items (log₂(8) = 3). Look hard at step 3: lo == hi and the loop still runs — that is exactly why the condition must be lo <= hi. When the target is missing, the same shrinking continues until hi slips below lo and the loop exits empty-handed.

Quiz

You binary search a sorted list for a value that is NOT there. How does a correct implementation finally stop?

The three classic bugs

Almost every broken binary search fails in one of three places. Memorize this checklist:

Loop condition is lo <= hi, not lo < hi. When lo == hi there is still one unchecked element.
Move past mid: lo = mid + 1 and hi = mid - 1. Using lo = mid can loop forever, because a two-element range keeps computing the same mid.
The list must be sorted. Binary search on unsorted data returns garbage without crashing, which is worse than crashing.

One more habit: say the invariant out loud. "The target, if it exists, is always inside [lo, hi]." Every line of the function exists to keep that sentence true.

Quiz

A sorted list has 1,000,000 items. Roughly how many checks does binary search need in the worst case?

Code exercise · python

Your turn. Modify binary search to also return how many checks it made: return (index, checks). Then run it on a million-item list to see the log₂ prediction come true.