Binary Search on the Answer

Turn an optimisation problem into a feasibility problem, then binary search. One of the highest-value patterns in competitive programming.

The pattern

optimise f(x)     -->     binary search x, asking "is x achievable?"

It applies whenever the feasibility predicate is monotone: if $X$ works, every larger (or every smaller) value works too.

long long lo = LOW, hi = HIGH, ans = -1;
while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (feasible(mid)) { ans = mid; hi = mid - 1; }   // minimising
    else lo = mid + 1;
}

Recognising it

The giveaway phrases:

Statement says	Predicate
”minimise the maximum…"	"can the maximum be $\le X$?"
"maximise the minimum…"	"can the minimum be $\ge X$?"
"minimum time / cost such that…"	"is $X$ enough?"
"largest $k$ such that…"	"does $k$ work?"
"minimum number of groups…"	"do $X$ groups suffice?”

Minimax and maximin objectives are almost always binary search. Recognising this replaces a hard DP with a greedy check.

Worked examples

Split an array into $k$ parts, minimising the largest part sum

bool feasible(long long X, int k) {
    int parts = 1; long long cur = 0;
    for (long long v : a) {
        if (v > X) return false;                      // a single element exceeds X
        if (cur + v > X) { parts++; cur = 0; }
        cur += v;
    }
    return parts <= k;
}
// binary search X in [max(a), sum(a)]

$O(n\log (\sum a))$ — versus $O(k{n}^2)$ for the DP. Always check for this before writing the DP.

Place $k$ cows in stalls maximising the minimum gap

feasible(d): greedily place cows at least $d$ apart; feasible iff at least $k$ fit.

Minimum capacity to ship all packages in $D$ days

feasible(cap): greedily fill days; feasible iff days used $\le D$.

$k$-th smallest element of an $n\times n$ sorted matrix

count(X): number of elements $\le X$, computed by a staircase walk in $O(n)$. Binary search $X$ over the value range: $O(n\log (\max -\min ))$.

Maximum average subarray of length $\ge L$

feasible(avg): subtract avg from every element; is there a subarray of length $\ge L$ with a non-negative sum? Computable with prefix sums and a running minimum in $O(n)$. Binary search avg over reals.

This last one — subtract the candidate average and look for a positive sum — is a technique worth internalising; it converts fractional objectives into linear ones.

Fractional programming (Dinkelbach)

To maximise $\frac{\sum a_i{x}_i}{\sum b_i{x}_i}$, binary search $\lambda$ and test whether $\sum (a_i-\lambda b_i)x_i\ge 0$ is achievable. Each test is a linear problem.

This solves:

• minimum ratio cycle (average edge weight) — see Karp;
• maximum density subgraph (with a min cut per test);
• optimal cost-to-time ratio scheduling.

Dinkelbach’s iteration (repeatedly setting $\lambda$ to the current best ratio) usually converges in a handful of steps — faster than binary search in practice.

Binary search + a data structure

The feasibility check can itself be non-trivial:

Check	Cost
Greedy scan	$O(n)$
DP	$O(n^2)$
Max flow	e.g. “can we schedule everything by time $X$“
Matching	”is there a perfect matching using only edges $\le X$” (bottleneck matching)
2-SAT	”is there an assignment with separation $\ge X$“
Connectivity	”is the graph connected using only edges $\le X$”

The combination binary search + 2-SAT and binary search + flow are both standard and worth recognising.

Pitfalls

Check monotonicity

If the predicate is not monotone, binary search returns an arbitrary boundary — plausible, and wrong. When unsure, brute-force feasible(X) for all $X$ on a small input and confirm the pattern is F...FT...T.

• Set hi to a provable upper bound; too small silently clamps the answer.
• With real values, use a fixed iteration count.
• With integers, decide whether you want the smallest true or the largest false, and stick to one template.

See also: Binary Search · Aliens Trick · Parallel Binary Search