Binary Search

Halve the search space each step. $O(\log n)$ — and the technique generalises far beyond “find a value in a sorted array”.

The template that never has off-by-one errors

Think of it as finding the boundary of a monotone predicate:

// find the smallest x in [lo, hi] with pred(x) true; assumes F,F,...,F,T,T,...,T
int lo = 0, hi = n;                       // hi is one past the last valid answer
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;         // avoids overflow
    if (pred(mid)) hi = mid;
    else           lo = mid + 1;
}
// lo == hi == the answer (or n if none)

The invariant is: pred is false everywhere below lo, and true at hi if anywhere. Writing it this way — one loop shape, one invariant — eliminates the classic off-by-one family.

For the largest $x$ with pred(x) true, search for the smallest false and subtract one, or mirror the template.

STL

lower_bound(a.begin(), a.end(), x);       // first >= x
upper_bound(a.begin(), a.end(), x);       // first > x
equal_range(a.begin(), a.end(), x);       // both
binary_search(a.begin(), a.end(), x);     // bool

Not on set/map

std::lower_bound(s.begin(), s.end(), x) on a set is $O(n)$ — the iterators are not random-access, so it degrades to a linear scan. Always use the member function s.lower_bound(x).

Real-valued binary search

double lo = 0, hi = 1e18;
for (int iter = 0; iter < 100; iter++) {  // fixed count, no epsilon comparison
    double mid = (lo + hi) / 2;
    if (pred(mid)) hi = mid; else lo = mid;
}

Use a fixed iteration count, not while (hi - lo > eps). 100 iterations halve the interval by $2^{100}$, which exhausts double precision — and the loop provably terminates, which the epsilon version does not when the values are large enough that hi - lo cannot shrink further.

Binary search on the answer

The most valuable form. If a predicate is monotone in the answer, binary search it and turn optimisation into a feasibility check:

Problem	Predicate
Minimise the maximum load	”can we do it with maximum $\le X$?”
Maximise the minimum gap	”can we place all items with gap $\ge X$?”
Minimum time to finish	”is $X$ time enough?”
$k$-th smallest in a matrix	”are there $\ge k$ elements $\le X$?”
Minimum capacity to ship in $D$ days	”does capacity $X$ suffice?”
Median of two sorted arrays	partition search
Maximum average subarray	”is there a subarray with average $\ge X$?” (subtract $X$, look for a positive sum)

See Binary Search on the Answer.

Binary search on other structures

Structure	Method
Sorted array	the classic
Answer value	binary search on the answer
A BIT	descend by powers of two — $O(\log n)$, no extra factor
A segment tree	descend the tree (“find the first index with prefix sum $\ge k$“)
A tree, by depth	binary lifting
Parallel over many queries	parallel binary search
A treap by subtree size	descend by size

BIT descent

int findKth(int k) {                       // smallest i with prefix(i) >= k
    int pos = 0;
    for (int pw = 1 << LOG; pw; pw >>= 1)
        if (pos + pw <= n && bit[pos + pw] < k) { pos += pw; k -= bit[pos]; }
    return pos + 1;
}

One descent instead of “binary search + prefix query” — saves a log factor.

Exponential (galloping) search

When the range is unbounded, first find a bracketing power of two, then binary search:

int hi = 1;
while (!pred(hi)) hi *= 2;
// now binary search in [hi/2, hi]

$O(\log (\text{answer}))$ rather than $O(\log (\text{range}))$ — useful when the answer is small but the range is $10^{18}$.

Common pitfalls

Four recurring bugs

1. (lo + hi) / 2 overflows when both are near INT_MAX. Use lo + (hi - lo) / 2.
2. Real-valued search with while (hi - lo > eps) can loop forever for large values.
3. The predicate must be monotone. Verify it — a non-monotone predicate gives a plausible wrong answer, not a crash.
4. Choosing hi too small silently clamps the answer. Set it to a provable upper bound.

See also: Binary Search on the Answer · Ternary Search · Parallel Binary Search