Binary Search on Answer
Turn optimization into repeated feasibility checks by designing a monotone predicate over the answer space.
Binary Search on Answer
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Binary search on answer is the pattern for optimization problems where the answer itself is not easy to construct directly, but feasibility at a fixed candidate value \(\lambda\) is easy to test.
When to Use It
Use it when:
the statement asks for a minimum feasible value or maximum feasible value,
there is a checker \(\texttt{can}(\lambda)\),
the checker is monotone over the searched answer space.
The usual contest phrasing is ``minimize the maximum'', ``maximize the minimum'', or ``find the first time / capacity / threshold where the plan becomes possible.''
Core Idea
Turn the optimization target into a yes/no predicate: \[ \texttt{can}(\lambda) = \text{``the problem is solvable if the answer is constrained by } \lambda \text{''}. \]
Then prove that once the predicate becomes true, it stays true forever, or once it becomes false, it stays false forever. Ordinary binary search finds the boundary.
Key Insight
The search loop is almost never the real difficulty. The real work is modeling. A good note to self is:
Do not start writing the binary search until the predicate and its monotonicity are both explicit.
Worked Problem
Problem.
An array of positive task durations must be partitioned into at most \(k\) consecutive days. Minimize the maximum total duration assigned to one day.
Why binary search fits.
Fix a candidate limit \(L\). The checker asks: can the tasks be split into at most \(k\) consecutive groups such that every group sum is at most \(L\)?
Checker.
Scan left to right and greedily extend the current day while the sum stays \(\le L\). When adding the next task would exceed \(L\), start a new day.
Why the checker is correct.
For positive tasks, postponing a split cannot hurt: every extra task only increases the current day's load. So the greedy scan uses the minimum possible number of groups for this limit. If even that greedy grouping needs more than \(k\) days, no other grouping can do better.
Why the predicate is monotone.
If limit \(L\) is feasible, then every larger limit is also feasible because the same partition still works.
Problem Pattern
This modeling trick reappears in:
maximum minimum distance under greedy placement,
machine-capacity or scheduling thresholds,
shortest time until a process can finish,
DP or prefix-sum checkers that become feasible past one boundary.
Correctness Intuition
Binary search itself contributes no special proof once the predicate is monotone. The proof burden sits entirely inside:
the checker correctness,
the monotonicity argument,
the bounds that guarantee the answer lies in the searched interval.
Complexity Analysis
If the checker costs \(T\) and the answer space size is \(A\), the total cost is \(O(T \log A)\).
For the partition example, the checker is linear, so the full solution is \(O(n \log \sum a_i)\).
Implementation
The code keeps:
a generic
first_truebinary search,a concrete checker for the partition problem,
a helper that returns the minimum feasible limit.
Common Pitfalls
Searching before proving monotonicity.
Picking bounds that do not actually contain the answer.
Using a slow checker so the outer \(\log\) factor is irrelevant compared to a better direct solution.
Applying integer binary search to a real-valued optimization problem without a precision plan.
Variants / Extensions
Real-valued answer search.
Parallel binary search for many offline queries.
Parametric search where the checker itself is another greedy or DP routine.
Practice Problems
Partition an array while minimizing the largest segment sum.
Place routers or cows while maximizing the minimum distance.
Find the smallest machine speed, budget, or threshold that makes a plan feasible.
References
Code
Contest-ready reference implementation for the idea explained above.
template <class F>
long long first_true(long long lo, long long hi, F pred) {
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (pred(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
bool can_partition_with_limit(const vector<long long>& a, int k, long long limit) {
int parts = 1;
long long current = 0;
for (long long x : a) {
if (x > limit) {
return false;
}
if (current + x > limit) {
++parts;
current = 0;
}
current += x;
}
return parts <= k;
}
long long minimize_max_segment_sum(const vector<long long>& a, int k) {
long long lo = *max_element(a.begin(), a.end());
long long hi = accumulate(a.begin(), a.end(), 0LL);
return first_true(lo, hi, [&](long long limit) {
return can_partition_with_limit(a, k, limit);
});
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.