Why the loop is right

Is the board this lesson reads closely. Its binary search panel marks lo, mid and hi over the sorted list 1 to 15, and one line underneath warns about the off-by-one: “nail the invariant (is hi inclusive? is the answer in [lo,hi]?) or you loop forever / skip it.” This lesson is that one line, taken seriously.

Before you start. Sorting & Searching gave you binary search: on a sorted list, look at the middle, throw away the half that cannot hold what you want, repeat, so a million items takes about twenty looks. Recursion & Dynamic Programming gave you recursion: a function that calls itself on a smaller copy of the problem, stopped by a base case it can answer directly.

The idea in 30 seconds

Binary search is short, and professional programmers still got it wrong nine times in ten in Bentley’s classes, because tests on easy examples pass.
A loop invariant is a sentence that is true before the first lap and after every lap. For binary search: if the target is anywhere, it is between lo and hi.
Four questions check a loop: true at the start, kept by every lap, useful when the loop stops, and the range shrinks every lap. Each off-by-one breaks one of them.
Induction proves a recursion: the base case is right, and each size is right if every smaller size is. So trust the smaller call and check your own step.
A greedy method is proved by an exchange argument: swap a best answer’s next piece for greedy’s choice and show nothing gets worse.

Read the story · Skip to the numbers