The sentence that stays true

Think of a number between one and a thousand. I can find it in ten questions — you already know the trick: ask “is it bigger than 500?”, then keep halving. Binary search is the algorithm everyone knows, which makes it the perfect place to show what knowing an algorithm actually means, because the code — five lines, a loop, two comparisons — is not the algorithm. The algorithm is a sentence:

“If the target is in the array at all, it’s somewhere between lo and hi.”

Everything else is bookkeeping in that sentence’s service. (An array, if the word is new to you, is simply a numbered row of values.) The sentence is trivially true at the start, when lo and hi span the whole array. The loop probes the middle and uses the answer to discard half the window — and here is the entire intellectual content of binary search: it discards half without looking at it. What licenses that? One assumption: the array is sorted. If the middle element is smaller than the target, then everything left of the middle is smaller still, so the target — if it exists — can’t be there. The sentence survives the cut. Computer scientists have names for the three roles in play: the pre-condition (sorted — the contract you must bring), the invariant (the sentence, kept true through every iteration), and the post-condition (what you’re owed at the end). When the window empties, the sentence is still true — “if it’s anywhere, it’s in this empty window” — which is a proof that it’s nowhere. Even the failure case is a theorem.

Watch it happen below: the outlined bar shows where the target really lives, and the sentence above the controls is checked — honestly, against the whole array — at every probe.

Now do the cruel experiment: shuffle the array, pick a target you can see sitting right there, and step through. At some probe, the middle element gives its answer, the code discards a half — and the sentence turns false, because the discarded half is where the target was. Notice what does not happen: no error, no exception, no slowdown. The loop finishes in its usual handful of steps and reports, with perfect confidence, that an element you can see on screen does not exist. An algorithm stripped of its pre-condition doesn’t become slow; it becomes a liar.

This is why the invariant, not the code, is the thing to know. If you remember the sentence, you can rederive the code at a whiteboard — every line is forced. And nearly every way to get binary search wrong is an invariant error wearing a disguise. The classic off-by-one bugs — hi = mid or hi = mid − 1? lo < hi or lo <= hi? — are all the same mistake: the coder never decided whether the sentence says “between lo and hi inclusive” or “up to but not including hi”. Decide the sentence and the symbols pick themselves. Even professionals fall here: binary search was published in 1946, yet a study in 1988 found most textbook versions were broken, and in 2006 Google’s Joshua Bloch discovered that the version he’d written for Java’s standard library — used by millions — had carried an overflow bug for nine years, in the one line everyone considered too obvious to check.

The halving also explains the speed, and the speed is the punchline of the pre-condition. Each probe cuts the window in two: a thousand elements need ten probes, a million twenty, a billion thirty. Sorting the array is what purchases that exponential discount — the pre-condition isn’t red tape, it’s the price paid in advance for the right to discard halves unseen.

Every essay in this strand is, underneath, this essay again. A stack, a heap, a balanced tree, a hash table — each is a sentence about its own insides, kept true by every operation, and each graph algorithm is a sentence swept across a frontier. Learn the sentences and the data structures stop being flashcards to memorise; they become things you could have invented yourself.