Binary search — theory and visualization

Binary search answers questions about a sorted sequence (or any situation where a predicate is false for small values and true for large ones — “binary search on the answer”).

You keep an interval [lo, hi] that must still contain the answer. Each step picks mid, compares or tests, and throws away half of the interval. After about log₂ n steps, only one plausible position remains.

Why sorting matters (array search): The comparison a[mid] vs target tells you whether the target can still live in the left half or only the right half. Without order, that inference is invalid.

Contest angle: Prefer lower_bound / upper_bound on vector when you only need a position — they encode correct edge cases. Hand-written loops are fine if you keep one clear invariant and test n = 0, n = 1, and “all equal.”

Assume 0-based indices and a non-decreasing array a.

1. Set lo and hi so the answer index is inside [lo, hi] (exact meaning depends on your variant: inclusive ends vs half-open interval).
2. mid = lo + (hi - lo) / 2 — use this form to avoid overflow on large indices in C++.
3. If a[mid] < target, the target (if it exists) lies strictly to the right of mid, so move lo past mid.
4. If a[mid] >= target, the first place that could be target (or the insert position) is at mid or left, so move hi toward mid.
5. Stop when the interval has shrunk to the answer.

Different problems use slightly different < vs <= and whether hi is inclusive. Pick one template, write check(mid) or a[mid] logic once, and reuse it.

Array a = [1, 3, 5, 7, 9, 11], target x = 7. We want the smallest index i with a[i] >= 7 (same spirit as lower_bound).

Use half-open invariant: lo is always valid (answer in [lo, hi)), hi is past-the-end of the candidate range. Start lo = 0, hi = 6 (length).

If x is not present, you still get the first index where you would insert x to keep order. If x is smaller than everything, answer is 0; if x is larger than everything, answer is n (past the end — often check lo == n as “not found” for strict existence queries).

• mid = lo + (hi - lo) / 2: avoids (lo + hi) overflow on large bounds.
• Know your invariant: write in a comment what [lo, hi] or [lo, hi) means and what is impossible outside it.
• Prefer STL on sorted vector: lower_bound, upper_bound, equal_range — fewer off-by-one bugs.
• lower_bound: first position with value ≥ x. upper_bound: first with value > x. Count of x: upper_bound - lower_bound.
• Monotone check(K): if check(K) is false for small K and true for large K, binary search the smallest good K. Reverse the if for largest good K.
• Bounds for “search on answer”: start from a definitely bad lo and definitely good hi (or the reverse), then shrink until hi - lo == 1 — many coders find that easier than while (lo < hi) with ambiguous ends.
• Sanity tests: n = 0, n = 1, all elements equal, target smaller than min / larger than max, answer at index 0 or n-1.
• Time: each step is O(1) or O(n) inside check — total is O(log n) or O(n log n) respectively; do not hide a linear check inside many iterations without noticing.
• Floating binary search: fixed number of iterations (e.g. 80–100) often beats fiddly epsilons for geometry or real outputs.

First index with value ≥ x (0-based, half-open [lo, hi)):

Each iteration cuts the remaining range by about half.