Checking a binary search before you run it
Four questions prove a binary search correct, and two tiny inputs catch almost every bug that slips past them.
Four questions
A binary search is short enough to prove on the whiteboard, and saying the proof aloud is worth more in an interview than a fast first draft. Ask:
- Start. Does the invariant hold before the first iteration? For "the first true is in [lo, hi]", the initial range must contain it, which is why the lower bound starts with hi = n.
- Each update. If the invariant holds at the top of the loop, does it hold after either branch? A pass on the first-true search keeps mid; a fail removes mid and everything to its left, which all fail too.
- Progress. Does every iteration make the range strictly smaller? This is the question that catches the infinite loop.
- Exit. When the loop stops, does the invariant name the answer? With lo = hi and the answer in [lo, hi], it is lo.
Ranges of size one and two
Question 3 is answered by checking the two smallest ranges by hand. A range of one element must end the loop or shrink to empty; a range of two must shrink whichever branch is taken.
| Template | Range | mid | Pass gives | Fail gives | Shrinks? |
|---|---|---|---|---|---|
| First true, mid rounded down | [3, 4] | 3 | [3, 3] | [4, 4] | yes |
| First true, mid rounded up | [3, 4] | 4 | [3, 4] | [5, 4] | no: a pass repeats |
| Last true, mid rounded up | [3, 4] | 4 | [4, 4] | [3, 3] | yes |
| Last true, mid rounded down | [3, 4] | 3 | [3, 4] | [3, 2] | no: a pass repeats |
| Exact match, lo ≤ hi | [3, 3] | 3 | returns | [4, 3] or [3, 2] | yes: empty |
The rule in one line: the update that keeps mid must be paired with the rounding that keeps mid away from that side.
Test it against a scan
When you can run code, the fastest check is a brute force beside the search. A linear scan for the first true is three lines and obviously right; compare the two on every small input.
Exhaustive check of a first-true search
check()
- For every length n from 0 to 8, and every split point s from 0 to n:
- build the test that is false below s and true from s on;
- run the search and confirm it returns s.
That is 45 cases and it covers every shape a monotone test can take on short inputs, including "nothing passes" and "everything passes". Every problem in this course is checked the same way: its tests come from an independent brute force, not from the solution being tested.
Overflow in the midpoint
(lo + hi) / 2 overflows when lo + hi exceeds the integer type, which happens with 32-bit
indices above about 1.07 × 10⁹ and, more often, with searches over answers whose bounds are large.
lo + (hi − lo) / 2 never does, as long as hi − lo fits.
| Language | Midpoint to write | Note |
|---|---|---|
| Python | (lo + hi) // 2 | integers do not overflow; // is the floor, also for negatives |
| C++, Java | lo + (hi − lo) / 2 | / truncates toward zero; with hi ≥ lo this is still the floor |
| Rust | lo + (hi − lo) / 2 | overflow panics in debug builds, wraps silently in release |
| JavaScript | lo + ((hi − lo) >> 1) | >> works below 2³¹; use Math.floor beyond that |
| Haskell | lo + (hi − lo) `div` 2 | Int is 64-bit; div is the floor |
The midpoint is not the only overflow. Checks that multiply (mid × mid, a rate times a count) need 64-bit arithmetic even when every input fits in 32 bits.