The Invariant-Driven Template

Why "the easy algorithm" ships with bugs constantly

Binary search is famously simple to describe and famously easy to get subtly wrong — a widely cited study found the majority of published binary search implementations, including ones in textbooks, contained bugs. The fix isn't memorizing a magic template; it's writing the loop from an explicit invariant, the same discipline every earlier module in this course has built toward. Get the invariant right, and the code follows mechanically. Skip it, and you're pattern-matching against half-remembered code, which is exactly how off-by-ones creep in.

The invariant, stated precisely

Searching a sorted array for target, maintain two pointers lo and hi such that:

The answer, if it exists, lies in [lo, hi] (inclusive on both ends). Everything outside this range has been proven NOT to be the answer.

This should look familiar — it's the exact shape of the elimination invariant from Two Pointers, specialized to a single search target instead of a pair. Think of it like searching for a word in a physical dictionary: you don't scan page by page — you crack it open near the middle, check which half the word falls in, and physically ignore the other half, repeating on the surviving half until one page is left. Each iteration examines the midpoint and, based on one comparison, proves an entire half is impossible and shrinks the range:

def binary_search(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr) - 1
    while lo <= hi:                        # range [lo, hi] non-empty
        mid = lo + (hi - lo) // 2           # avoid overflow (see below)
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1                    # arr[lo..mid] all < target: eliminate
        else:
            hi = mid - 1                    # arr[mid..hi] all > target: eliminate
    return -1                               # range emptied: target absent

Why arr[mid] < target eliminates the entire left half through mid, not just mid itself: sortedness guarantees everything at indices ≤ mid is ≤ arr[mid] < target, so none of them can equal target either. One comparison, half the remaining range eliminated — the same batch-elimination shape, just cutting a single range in half instead of shrinking from two ends.

The five decisions that cause every bug

1. lo <= hi vs. lo < hi. The loop condition must match the invariant: since [lo, hi] is inclusive and can be a single element (lo == hi), the loop must still run in that case — lo <= hi is correct. Using lo < hi would skip checking the last remaining candidate.

2. mid = lo + (hi - lo) // 2, not (lo + hi) // 2. In languages with fixed-width integers, lo + hi can overflow before the division happens, if both are large. Concretely: in a 32-bit signed integer (max ≈2.1 billion), lo = 1.4 billion, hi = 1.5 billion gives lo + hi ≈ 2.9 billion — past the limit, wrapping to a negative number before the /2 ever runs. lo + (hi - lo) // 2 never sums the two large numbers directly: hi - lo is the (small) distance between them, half of that is added back to lo, and the running total never exceeds hi. JavaScript's numbers don't overflow the same way at typical array sizes, but the habit transfers directly to languages that do (Java, C++) — worth building now.

3. mid + 1 / mid - 1, never mid. Once arr[mid] has been ruled out (it's not the target and we know which side it's on), it must be excluded from the new range — including it again would either loop forever (if mid never changes) or silently re-examine an already-eliminated element. Watch it fail on arr = [1, 3], target = 3, with the buggy update lo = mid (instead of lo = mid + 1): lo=0, hi=1 → mid = 0, arr[0]=1 < 3, buggy update sets lo = mid = 0 — unchanged. Next iteration: same lo=0, hi=1, same mid = 0, same update, same result. lo never moves again; integer division's truncation keeps pulling mid back down to 0 forever. The +1 isn't a style preference — it's what actually guarantees the range shrinks.

4. What the invariant claims when the loop ends. lo > hi means the range has been proven empty — every index was checked or eliminated with a proof — so returning "not found" is airtight, not a guess.

5. Which half a comparison eliminates. Always eliminate the side that CANNOT contain the answer, and always keep mid itself accounted for exactly once (either it's the answer, or it's provably excluded from [lo, hi] next iteration — never both kept and re-examined).

Step through a search and watch the eliminated half turn red at every comparison — one comparison, half the live range gone, proof included:

Why this generalizes past "find a value in a sorted array"

The invariant never actually required the array to be sorted VALUES — it required that comparing against arr[mid] reliably tells you which half to eliminate. That's a weaker, more general condition: what it really needs is a monotonic predicate — some boolean function of position that is false for a prefix and true for a suffix (or vice versa), with no flip-flopping. "Is arr[i] >= target?" is monotonic on a sorted array. So is "can Koko eat all the bananas at speed k?" on the range of possible speeds — no sorted array in sight. The next two lessons build exactly this generalization: first to finding a boundary within a monotonic predicate, then to searching an answer space that was never an array at all.