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.
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
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 leastx, keep the left half by settinghi = mid. - Otherwise eliminate
midand the entire left half by settinglo = mid + 1.
Common mistakes
- Students often update
lo = midorhi = mid - 1without 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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Bipartite Matching, Augmenting Paths, and Assignment Structure.
Least You Need to Know: Bipartite Matching, Augmenting Paths, and Assignment StructureRelated lessons
Keep going with nearby lessons in the same topic.