i. Binary Search

Binary search finds the boundary of a monotone predicate in $O(\log (\text{range}))$ evaluations. Searching a sorted array is the least interesting use. The big ones are binary searching the answer of an optimisation problem, and descending a data structure.

One template, one invariant

// predicate is F F ... F T T ... T on [lo, hi); find the first T (or hi if none)
ll lo = LO, hi = HI;            // invariant: pred false on [LO, lo), true on [hi, HI)
while (lo < hi) {
    ll mid = lo + (hi - lo) / 2;  // floor division for lo >= 0; use (lo + hi) >> 1 with negatives
    if (pred(mid)) hi = mid; else lo = mid + 1;
}
// lo == hi == first true

• For the last true in a T...T F...F predicate, search the first false and subtract one.
• Alternative form that some people prefer: keep l always false and r always true, loop while (r - l > 1), and the answer is r. Pick one form and never mix them.
• hi must be a provable bound. Too small silently clamps the answer; too large can overflow inside pred (for example mid * mid with mid near $10^{18}$).
• (lo + hi) / 2 rounds toward zero, which breaks the invariant when the range includes negatives. lo + (hi - lo) / 2 or (lo + hi) >> 1 (arithmetic shift is floor) are safe.

Proof: the template terminates and is correct

Invariant maintained. Before the loop, pred is (vacuously) false on $[LO,lo)=\varnothing$ and true on $[hi,HI)=[LO,HI)$ is not required yet — the real starting invariant is just “false below lo, true at or above hi” with lo=LO,hi=HI bounding the unknown region. Each step computes mid strictly between lo and hi (since lo<hi), and: if pred(mid) is true, setting hi=mid keeps “true at/above hi” (mid itself is now confirmed true, and the invariant extends down to it) without touching the false region; if false, setting lo=mid+1 keeps “false below lo” (mid is now confirmed false, extending the false region up through it). Monotonicity of pred (false-then-true) is exactly what guarantees no update ever has to revise an earlier region.
Termination. mid strictly between lo and hi means either hi decreases to mid<hi or lo increases to mid+1>lo, so hi-lo strictly decreases every iteration (it does not just stay the same), hence the loop runs $O(\log (HI-LO))$ times and terminates with lo==hi.
Correctness at exit. When lo==hi, the invariant “false below lo, true at/above hi” with lo=hi says exactly: false on $[LO,lo)$, true on $[lo,HI)$ — so lo is the first true, exactly as claimed (or HI itself if pred is false everywhere on $[LO,HI)$, since hi never decreases past a true position). $■$

Bitwise descent is the same search written over bits. It finds the largest $x<2^K$ with pred(x) true when the predicate is T..T F..F, and it’s the shape used by Fenwick and binary-lifting descents:

ll x = 0;
for (int b = K - 1; b >= 0; b--) if (pred(x | 1LL << b)) x |= 1LL << b;

STL

Call	Returns
lower_bound(all(a), x)	first $\ge x$
upper_bound(all(a), x)	first $>x$
upper_bound - lower_bound	count of $x$
prev(lower_bound(...))	last $<x$ (check begin)
partition_point(all(a), pred)	first element where pred is false (pred must be T..T F..F)
ranges::lower_bound(a, x, {}, &T::key)	projection onto a field

On set/map use the member s.lower_bound(x). The free function is $O(n)$ on non-random-access iterators.

Real-valued search

double lo = 0, hi = 1e9;
for (int it = 0; it < 100; it++) {           // fixed count: always terminates
    double mid = (lo + hi) / 2;
    (pred(mid) ? hi : lo) = mid;
}

while (hi - lo > eps) can loop forever: when values are around $10^9$ a double can’t represent a difference of $10^{-9}$. 100 iterations exhaust double precision for any range. For a relative-precision answer spanning many magnitudes, search on $\log x$ or bisect the bit pattern of the double.

Binary search on the answer

If “can we achieve $X$?” is monotone in $X$, optimisation becomes feasibility. The statement phrases are “minimise the maximum”, “maximise the minimum”, “minimum time such that”, “largest $k$ such that”.

Problem	Feasibility check for $X$
split array into $\le k$ parts minimising the max sum	greedy: cut when the running sum would exceed $X$
place $k$ points maximising the minimum gap	greedy from the left
$k$-th smallest pairwise sum / distance / product	count pairs $\le X$ with two pointers, $O(n)$ per check
$k$-th smallest in an $n\times n$ row/column-sorted matrix	staircase count, $O(n)$
$k$-th smallest of $a_i{b}_j$ with signs	count with two pointers on sorted positive/negative parts
max average subarray with length $\ge L$	subtract $X$, then check for a non-negative sum of length $\ge L$ using prefix minima
max median of a subarray with length $\ge L$	map to $\pm 1$ by comparing with $X$, same check
minimum time for $n$ machines to make $m$ items	$\sum \lfloor X/t_i\rfloor \ge m$ (watch overflow: cap the sum)
minimum largest edge so that the graph is connected / has a perfect matching / 2-SAT holds	rebuild with edges $\le X$
minimum radius / time with a geometric condition	real binary search + check
minimum $\max$ with a DP inside	the DP becomes simpler with a fixed threshold

Combinations worth recognising: binary search + 2-SAT (separation constraints), binary search + max flow (scheduling by a deadline), binary search + matching (bottleneck assignment), binary search + shortest path (minimise the maximum edge, or a parametric cost), binary search + DP (the check re-runs a $O(n^2)$ or cheaper DP with the threshold baked in — often simpler than the unconstrained DP, since fixing $X$ removes a dimension).

Fractional programming

To maximise $\frac{\sum a_i{x}_i}{\sum b_i{x}_i}$ ($b>0$) over a feasible set, binary search $\lambda$ and check $\max \sum (a_i-\lambda b_i)x_i\ge 0$, which is a linear objective. Dinkelbach’s iteration is faster in practice: ${\lambda }_{t+1}=\frac{\sum a_i{x}_i^{\ast }}{\sum b_i{x}_i^{\ast }}$ where $x^{\ast }$ is optimal for ${\lambda }_t$. It converges superlinearly, usually in 5-10 rounds.

Uses: minimum mean cycle, optimal ratio spanning tree, maximum density subgraph (each check is a min cut), “best average” knapsack (choose $k$ items maximising $\sum a/\sum b$: sort by $a-\lambda b$).

When the check costs a log too

Total cost is $O(\log (\text{range})\cdot \text{check})$. If both the outer search and the check are $O(\log )$, consider descending a structure instead (below). If there are many independent searches over the same sequence of updates, use parallel binary search.

Searching inside a structure

Structure	Descent
Fenwick tree	find the smallest prefix with sum $\ge k$ in $O(\log n)$ by bitwise descent, instead of $O({\log }^{2}n)$
segment tree	max_right(l, pred) / min_left: walk down to the first index where the aggregate stops satisfying pred
treap / order-statistic tree	descend by subtree sizes for $k$-th or rank
tree ancestors	binary lifting: jump $2^j$ while the condition holds (first ancestor with value $\ge x$, LCA)
wavelet tree / persistent segment tree	$k$-th smallest in a range by descending on counts
convex hull / sorted angles	binary search the tangent or the sector

int bitLowerBound(ll k) {            // Fenwick t[1..n] (non-negative values), smallest i with prefix(i) >= k
    int pos = 0;
    for (int pw = 1 << __lg(n); pw; pw >>= 1)
        if (pos + pw <= n && t[pos + pw] < k) pos += pw, k -= t[pos];
    return pos + 1;
}

Proof: bitLowerBound is correct

Standard Fenwick indexing means t[pos+pw], when pos has its lowest pw-and-below bits all zero (an invariant maintained by only ever adding powers of two in decreasing order), stores the sum of the range $(pos,pos+pw]$ — exactly the next $pw$ elements’ total starting after pos. The loop tries every power of two from largest to smallest, in the same order a binary representation of the answer’s offset from pos would be built: if the block $(pos,pos+pw]$ sums to less than the remaining target $k$, that whole block can be safely skipped (it cannot contain the crossing point, since even including all of it doesn’t reach $k$) — so pos advances by pw and k decreases by the block’s sum (accounting for what’s now “used up”); otherwise the block does contain the crossing point, so pw is skipped and a finer power of two is tried within the same remaining range. This is bitwise descent (proved in general above) applied with the Fenwick tree’s own binary decomposition as the bit source, giving $O(\log n)$ instead of binary-searching prefix sums with an extra $O(\log n)$ query each ($O({\log }^{2}n)$). Non-negative values are required for monotonicity of the prefix sum (the predicate “prefix $\ge k$” must be a true $F\dots FT\dots T$ pattern). $■$

Tested against brute-force linear scan for the smallest prefix $\ge k$, on random non-negative Fenwick arrays.

Other forms

• Exponential (galloping) search. Double hi until pred(hi) holds, then binary search $[hi/2,hi]$. It costs $O(\log \text{answer})$, which matters when the answer is small but the range is $10^{18}$ or unbounded.
• Integer roots. $\lfloor \sqrt[k]{n}\rfloor$ by binary search with overflow-safe power (stop multiplying once the product exceeds $n$), or pow followed by $\pm 1$ correction.
• Median of two sorted arrays. Binary search the split of the shorter array so that left parts are all $\le$ right parts: $O(\log \min (n,m))$. Generalises to the $k$-th element of two sorted arrays.

Proof: the median-of-two-sorted-arrays search

For a candidate split $i$ in array $A$ (size $n$) putting $A[\mathrm{0..}i)$ on the left, the matching split $j=k-i$ in $B$ (size $m$, $k$ = half the combined length) is forced by needing exactly $k$ elements total on the left. The split is valid (the left half is entirely $\le$ the right half) iff $A[i-1]\le B[j]$ and $B[j-1]\le A[i]$ (boundary comparisons, with sentinels $\pm \infty$ at the edges). As $i$ increases by 1, $j$ decreases by 1 (to keep the total at $k$), so $A[i-1]$ is non-decreasing and $B[j-1]$ is non-increasing in $i$ — meaning "$A[i-1]\le B[j]$" flips from true to false at most once as $i$ increases (monotone predicate), and symmetrically for the other condition. So the valid split (if it exists, and it always does for a well-formed input) is found by binary searching $i$ for the point where both conditions hold — a standard monotone-predicate search, giving $O(\log n)$ by searching the shorter array (searching the longer would cost $O(\log m)$ unnecessarily when $m>n$). $■$

• Interpolation search. $O(\log \log n)$ on uniformly distributed keys, $O(n)$ worst case. Rarely useful in contests.
• Binary search over a permutation of candidates. If the predicate is monotone in a sorted order of objects (edges by weight, times of events), sort the objects and binary search the index.
• Interactive binary search. The budget $\lceil {\log }_{2}n\rceil$ is tight, so every query must halve the candidates exactly (Interactive).

Pitfalls

Verify monotonicity

A non-monotone predicate gives a plausible wrong answer, not a crash. On a small input, brute-force pred(X) for every $X$ and check the pattern is F..FT..T.

• Off-by-one: decide whether you search the first true or the last true, and write it in a comment.
• Overflow inside the check: sums of $\lfloor X/t_i\rfloor$, products mid * mid, counts of pairs. Cap them or use __int128.
• Real searches with an epsilon loop: use a fixed iteration count.
• The answer may be “impossible”: check pred(HI) before trusting the result.