Skip to main content

Binary Search and Its Invariant: Correctness as a Template

What This Concept Is​

Binary search finds a target in a sorted array in (\Theta(\log n)) time by maintaining a shrinking candidate region.

The textbook form (closed interval [lo, hi]):

def binary_search(A, target):
    lo, hi = 0, len(A) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if A[mid] == target:
            return mid
        if A[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

The invariant is:

At the start of each iteration, if target is in A, it is in A[lo..hi].

The correctness proof is a direct check that each branch preserves this statement, and termination follows because hi - lo strictly decreases. The comparison count is (\lceil \log_2(n + 1) \rceil) in the worst case, which matches the decision-tree lower bound for searching a sorted array of (n+1) possible outcomes (each index, or "not found").

More broadly, binary search applies anywhere you can ask a monotone predicate -- "is the answer at least (x)?" -- about positions or values, not just whole keys. This generalization is called binary search on the answer or parametric search, and it is the workhorse of contest problem-solving and of many system capacity calculations.

Distinguish the two conventions that both appear in real code:

  • Closed interval [lo, hi] with while lo <= hi and hi = mid - 1 on the right-shrink branch.
  • Half-open interval [lo, hi) with while lo < hi and hi = mid on the right-shrink branch.

Both are correct; both correspond to different invariants. Mixing conventions across a single function is where most off-by-one bugs live.

Why It Matters Here​

Binary search is the shortest famous algorithm that gets written incorrectly more often than it gets written correctly. Writing it as an invariant, not a trick, is how you avoid off-by-one bugs forever. Jon Bentley's canonical essay found that the majority of textbook implementations had the integer-overflow bug in mid = (lo + hi) / 2 until the mid-2000s; JDK shipped it for years.

The invariant template also generalizes:

  • lower_bound (first index (\geq x)): different invariant, different branch
  • upper_bound (first index (> x)): different invariant
  • binary search on the answer (smallest feasible value): replaces the array with a predicate
  • two-pointer shrinking and parametric search all reuse the "maintain an invariant on a candidate region" habit
  • exponential/galloping search for unbounded arrays: doubles a bound, then binary-searches

If you only memorize one form of binary search, you will write bugs when the problem asks for anything else. If you memorize the invariant, you can re-derive every variant in two lines.

Concrete Examples​

Example 1 -- search on an array. Search for 7 in A = [1, 3, 5, 7, 9, 11, 13]:

lo=0, hi=6, mid=3, A[mid]=7  -> return 3

Search for 8 in the same array:

lo=0, hi=6, mid=3, A[mid]=7 < 8  -> lo=4
lo=4, hi=6, mid=5, A[mid]=11 > 8 -> hi=4
lo=4, hi=4, mid=4, A[mid]=9 > 8  -> hi=3
lo=4, hi=3  -> exit, return -1

At every iteration, the invariant held: if 8 were in A, it would be in A[lo..hi]. When the region becomes empty, the invariant forces "not present."

Example 2 -- binary search on the answer. Given n = 1000 pages to distribute among k = 7 workers, each taking a contiguous batch, find the minimum possible "maximum load."

Define the predicate (P(L)) = "can we distribute the pages so each worker's load is (\leq L)?" (P) is monotone: if we can do it with bound (L), we can also do it with any (L' > L). Lower bound (= \max(\text{page counts})); upper bound (= \sum(\text{page counts})). Binary-search the smallest (L) for which (P(L)) is true, evaluating (P) by a greedy sweep in (\Theta(n)). Total: (\Theta(n \log(\sum))) -- strictly better than trying every candidate.

The predicate feasible(L) returns true iff we can partition the array into (\leq k) contiguous groups each of sum (\leq L). Binary search over integer (L) in ([\max(a), \sum(a)]). The answer is the first (L) with feasible(L) == true.

Common Confusion / Misconceptions​

The mid = (lo + hi) / 2 overflow bug. In languages with fixed-width integers for very large lo + hi (array sizes above (2^{30}) on 32-bit systems), the sum overflows. Use lo + (hi - lo) // 2 to avoid it. This is the bug that lived in java.util.Arrays.binarySearch until 2006.

Mixing half-open and closed intervals. while lo <= hi with hi = mid - 1 is the closed-interval pattern. while lo < hi with hi = mid is the half-open pattern. If you mix them (e.g., while lo <= hi with hi = mid), you get infinite loops when lo == hi == mid. Pick one convention per function and write a comment stating which.

"Binary search needs sorted data." True for the array form. False for binary-search-on-the-answer: there, the predicate needs to be monotone, not the data. Many contest problems secretly admit binary search because their feasibility predicate is monotone, not because anything is sorted.

"Binary search always needs (\Theta(\log n)) comparisons." True for the comparison count, but the cost is (O(\log n \cdot C)) where (C) is predicate evaluation cost. On a red-black tree in memory it is nanoseconds; on a remote service call with network latency, each "comparison" is a round trip and (\log n = 30) iterations means 30 round trips. Reach for galloping search + local cache when that matters.

How To Use It​

Template to follow every time:

  1. Decide the region: closed [lo, hi] or half-open [lo, hi).
  2. State the invariant in one sentence: "if the answer exists, it is in the region."
  3. Compute mid safely: lo + (hi - lo) // 2 (or std::midpoint(lo, hi) in C++20).
  4. For each branch, show that the invariant is preserved after the update.
  5. Show the region strictly shrinks so the loop terminates.
  6. State the post-condition at loop exit and return the derived index.
  7. Test on: empty array, single-element array, target at both ends, target not present, duplicates.

For predicate-based binary search ("smallest (k) such that (P(k)) is true"), replace A[mid] with P(mid) and require that (P) is monotone non-decreasing on the region. Use the same template for lower_bound, upper_bound, and "first/last occurrence" queries -- each changes only the branch condition.

Transfer / Where This Shows Up Later​

  • S2 M2 (this module). Binary search underpins many algorithms in concept 09 (selection in quickselect's worst-case analysis) and concept 10 (search on sorted-array containers).
  • S2 M3 (graphs). Bellman-Ford bound tightening and shortest-path algorithms over weighted graphs use binary-search-on-the-answer for bottleneck shortest path and binary lifting for LCA in (O(\log n)) per query.
  • S2 M4 (dynamic programming). Longest Increasing Subsequence in (\Theta(n \log n)) uses binary search on the patience-sort piles; binary search on the answer underlies several parametric DP speedups.
  • S3 (software design). Interval arithmetic, feature-flag rollout percentages, and capacity planning all rely on binary search on a monotone predicate.
  • S4 (systems programming). Kernel data structures (kallsyms lookup, symbol resolution) binary-search sorted address tables. Every debugger symbol table uses this.
  • S5 (OS). Page table walks for sparse address ranges and vma rbtree lookup are binary-search-shaped. IO scheduler merges use binary search on sector numbers.
  • S6 (databases). B+tree index lookup is binary search on disk, with fan-out to reduce the depth; range scans binary-search the start and end. Sort-merge join binary-searches the inner relation for each outer tuple when the ratio is skewed.
  • S7 (architecture). API contract compatibility checks ("does this version accept field X?") binary-search a sorted version axis.
  • S8 (system design). Consistent-hashing ring lookup is binary search on a sorted ring of hash values; rate-limiter token buckets binary-search monotone time predicates for precise throttle points.

Check Yourself​

  1. Why does hi = mid - 1 pair with while lo <= hi but hi = mid pair with while lo < hi?
  2. What exactly has to be true of a predicate (P) for predicate-based binary search to be correct?
  3. Why is mid = lo + (hi - lo) // 2 safer than mid = (lo + hi) // 2?
  4. How do lower_bound and upper_bound differ in their branch conditions, and why does that difference matter for counting occurrences?
  5. Why is binary search ill-suited for large-latency predicates, and what algorithm replaces it?

Mini Drill or Application​

  1. Write lower_bound(A, x) returning the smallest index i with A[i] >= x. Declare the invariant before coding.
  2. Use binary search on the answer to solve: given n pages and k workers, what is the minimum maximum load if each worker takes a contiguous batch? Define the predicate and bounds.
  3. Prove by induction on hi - lo that the textbook binary search terminates.
  4. Implement std::equal_range-style lookup (first and last occurrence) with two calls to binary search. Verify on [1,2,2,2,3,4,4,5].
  5. Write galloping search: given an unbounded sorted stream, find the target in (\Theta(\log i)) comparisons where (i) is the target index. Walk through the correctness argument.

Read This Only If Stuck​