Binary Search Beyond the Basics

Binary search is the first algorithm most competitive programmers learn and the last one they fully master. The simple version — find a value in a sorted array — is a warm-up problem. The real skill is binary searching on the answer space.

The Core Insight

Binary search works whenever you have a monotone predicate: a function $f(x)$ that is false for small $x$ and true for large $x$ (or vice versa). You don’t need an array at all.

The template:

int lo = 0, hi = 1e9;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (check(mid)) {
        hi = mid;      // mid is feasible, look left
    } else {
        lo = mid + 1;  // mid is not feasible, look right
    }
}
// lo == hi == answer

The art is writing check(mid).

Example: Koko Eating Bananas

Given piles of bananas, find the minimum eating speed $k$ such that you can eat all piles in $h$ hours.

The predicate: “can I eat all bananas at speed $k$?”

bool check(vector<int>& piles, int k, int h) {
    long long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;
    return hours <= h;
}

This predicate is monotone: too slow → false, fast enough → true. Binary search over $[1, \max(piles)]$.

Example: Aggressive Cows (Classic)

Place $c$ cows in $n$ stalls. Maximize the minimum distance between any two cows.

Predicate: “can I place $c$ cows such that any two are at least $d$ apart?”

bool check(vector<int>& stalls, int c, int d) {
    int placed = 1, last = stalls[0];
    for (int i = 1; i < stalls.size(); ++i) {
        if (stalls[i] - last >= d) {
            ++placed;
            last = stalls[i];
        }
    }
    return placed >= c;
}

Sort stalls first, then binary search over $d \in [1, stalls.back() - stalls.front()]$.

Floating-Point Binary Search

For geometry or physics problems, binary search over real numbers:

double lo = 0, hi = 1e9;
for (int iter = 0; iter < 100; ++iter) {
    double mid = (lo + hi) / 2;
    if (check(mid)) hi = mid;
    else lo = mid;
}

100 iterations gives precision around $10^-30$ — far beyond the $10^-6$ most problems ask for.

Common Mistakes

1. Integer overflow in mid — always use lo + (hi - lo) / 2, never (lo + hi) / 2.
2. Wrong loop invariant — decide: does hi = mid or hi = mid - 1? It depends on whether mid itself can be the answer.
3. Off-by-one on bounds — set hi to one past the valid range if needed.

Practice Problems

Once you internalize “binary search the answer,” you’ll start seeing monotone predicates in problems that look nothing like search problems. That’s the breakthrough moment.