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.
جو کم از کم جاننا ضروری ہے
- 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.
اہم علامتیں
lo, hi
current candidate range
mid
middle index or middle candidate
invariant
property that remains true after each update
مختصر حل شدہ مثال
- 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`.
عام غلطیاں
- 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.
اس قسم کے سوال کو کیسے پہچانیں
- 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.