Binary Search

What you're seeing

The bars are a sorted array (binary search needs that). The dashed line is the value you're looking for. At each step the algorithm probes the middle of the live window (blue) and compares it to the target: if the bar is below the line, the target must be further right, so the entire left half — and the probe — go dim; if above, the right half goes dim. The bright window halves every step until it either lands on the target (green) or collapses to nothing (the target wasn't there).

The rule

binary_search(a, target):     # a is sorted
    lo = 0;  hi = n - 1
    while lo <= hi:
        mid = (lo + hi) / 2       # floor
        if a[mid] == target: return mid
        if a[mid] <  target: lo = mid + 1   # target is to the right
        else:                hi = mid - 1   # target is to the left
    return NOT_FOUND              # window empty

One comparison throws away half of what's left. Every probe is counted in the readout.

The invariant

The guarantee is a containment: if the target is in the array, it is always inside the live window a[lo..hi]. It holds at the start (the window is the whole array). Each step preserves it: because the array is sorted, a[mid] < target means every index ≤ mid holds a value < target, so the target (if present) must be at an index > mid — exactly the half we keep; the mirror argument handles a[mid] > target. So we never discard the answer. Termination: the window strictly shrinks each step, so it either contains the target when probed or becomes empty — and an empty window, by the invariant, proves the target is absent. Correctness for the "not found" case is just as rigorous as for "found."

The cost

The window starts at size n and halves each probe, so it takes at most ⌊log₂ n⌋ + 1 probes to reach size 1 — searching a million sorted items costs about 20 comparisons. That logarithmic scaling is the whole point: drag the size slider far right and watch the probe counter barely move. The catch is the precondition: the data must already be sorted, which costs Θ(n log n) up front. Binary search pays off when you sort once and search many times.

In the wild

Binary search underlies database B-tree indexes, std::lower_bound / bisect / Arrays.binarySearch, version-control git bisect (binary-searching commits for the one that introduced a bug), and any "search a sorted column" query. It also generalizes far beyond lookups: binary search on the answer solves optimization problems by testing a monotone predicate (e.g. "can we finish in ≤ T time?") and halving the candidate range. Famously, it is also a minefield: Jon Bentley reported that most professional programmers cannot write it bug-free on the first try, and the canonical mid = (lo + hi) / 2 harbored an integer-overflow bug that sat in the JDK for years (fixed to lo + (hi − lo) / 2). Simple to state, surprisingly easy to get wrong.

References

1. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching, §6.2.1 (Searching an Ordered Table) — and the history of how hard it is to get right. Addison-Wesley.
2. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), Exercise 2.3-6 and §B. MIT Press, 2022.
3. Bentley, J. Programming Pearls, 2nd ed., Ch. 4 ("Writing Correct Programs") — the binary-search correctness case study. Addison-Wesley, 2000.
4. Bloch, J. "Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken." Google Research blog, 2006 — the (lo+hi)/2 overflow bug.