Algorithms / Binary Search Invariants
Least You Need to Know: Binary Search Invariants and Boundary Updates
Binary search works because the search interval maintains an **invariant**: the desired answer is still inside the remaining range. Each comparison must eliminate only the half that is provably impossible, and the boundary update must match the exact question being asked.
The least you need to know
- Binary search is about keeping the target or boundary answer inside a shrinking range.
- You need a sorted order or a monotone condition so one side can be ruled out safely.
- The loop update depends on whether you are searching for an exact value, the first true index, or the last false index.
- Midpoint comparisons are useful only when they justify discarding one half completely.
- Off-by-one errors usually come from updating a boundary that might still contain the answer.
Key notation
lo, hi
current candidate range
mid
middle index or middle candidate
invariant
property that remains true after each update
Tiny worked example
- Suppose you want the first index whose value is at least `x`.
- Keep the invariant that the answer is somewhere in `[lo, hi]`.
- If `a[mid]` is already at least `x`, keep the left half by setting `hi = mid`.
- Otherwise eliminate `mid` and the entire left half by setting `lo = mid + 1`.
Common mistakes
- Students often update `lo = mid` or `hi = mid - 1` without checking whether mid could still be the boundary answer.
- Students often say 'binary search' even when the condition is not monotone.
- Students often memorize a template without stating the invariant that makes the template safe.
How to recognize this kind of problem
- The array or answer space is sorted or behaves monotonically.
- The prompt asks for a boundary like first valid, first at least, or smallest feasible.
- A midpoint test can eliminate one whole side at a time.