Binary Search on the Answer: Monotone Predicates in C++
Binary search on the answer turns "find the least X that works" into a yes/no check and about 60 halvings. The template, monotonicity and C++ overflow traps.
- Course: Competitive Programming study plan
- Module: Binary search on the answer
- Kind: Lesson
- Reading time: 14 min
- Runtime: Clang 18 · C++20
What is binary search on the answer?
Binary search on the answer is a technique for optimisation problems whose feasibility is monotone: if a value X works, every larger X works too. Instead of computing the best X directly, you write a check ok(X) and binary search the range of possible answers for the first X where it says yes. The cost is the check times about log2 of the range, roughly 30 to 60 checks.
Lesson
Some problems ask for the best value directly — "the smallest largest part", "the largest smallest gap" — and computing it is hard. Checking a guess is easy. Binary search on the answer turns the hard question into about sixty easy ones.
The shape to look for
- The statement says minimise the maximum or maximise the minimum.
- For a fixed guess
Xyou can answer "is X achievable?" quickly, usually greedily in O(n). - The answers are monotone: once
Xworks, every biggerXworks too (or every smaller one, for a maximum). The row of answers reads no, no, …, no, yes, yes, …, yes.
That row is a sorted array of booleans, and binary search finds its first yes in log₂(range) steps.
Watch it halve
Split [7, 2, 5, 10, 8] into k = 2 contiguous parts so the largest part sum is as small as possible. The check for a limit X: walk left to right, start a new part whenever the next number would push the current one past X, and count the parts.
a = [7, 2, 5, 10, 8], k = 2- No split can beat the largest element, 10, and one part holding everything sums to 32. So the answer lies in [10, 32]: 23 candidates, and the search will check only a handful.
- mid = 21: the sweep makes 2 parts (sums 14 and 18), within k = 2. 21 works, so the answer is 21 or smaller: hi = 21.
- mid = 15: the sweep needs 3 parts (sums 14 and 10 and 8), more than k = 2. 15 fails, and so does everything below it: lo = 16.
- mid = 18: the sweep makes 2 parts (sums 14 and 18), within k = 2. 18 works, so the answer is 18 or smaller: hi = 18.
- mid = 17: the sweep needs 3 parts (sums 14 and 10 and 8), more than k = 2. 17 fails, and so does everything below it: lo = 18.
- lo and hi meet at 18: 4 checks instead of 23. The split [7, 2, 5] + [10, 8] has largest sum 18, and no split does better.
The answer can never be below the largest element (10) or above the total (32), so those are the bounds. Every check throws away half of what is left.
The template
ll lo = *max_element(a.begin(), a.end()); // certainly the floor
ll hi = accumulate(a.begin(), a.end(), 0LL); // certainly feasible
while (lo < hi) {
ll mid = lo + (hi - lo) / 2; // rounds down
if (ok(mid)) hi = mid; // mid works: the answer is mid or left of it
else lo = mid + 1; // mid fails: the answer is right of it
}
// lo == hi == the first X with ok(X)- Minimise (first yes):
hi = mid/lo = mid + 1,midrounds down. - Maximise (last yes):
lo = mid/hi = mid - 1,mid = lo + (hi - lo + 1) / 2rounds up — or the loop sticks on a two-value range. lo + (hi - lo) / 2never overflows;(lo + hi) / 2can when both are near 10^18.
The traps
- Sums in
int. A part sum of 10^5 values up to 10^9 is 10^14. Uselong longfor the range and the check. - A check that overflows. Counting "products made by time T" adds up to n values of
T / t, each up to 10^18. Stop as soon as the count reaches the target. - Wrong bounds. If
himight be infeasible, the search returnshianyway. Prove both bounds from the constraints.
More practice
- Koko Eating Bananas — minimise a speed.
- Capacity To Ship Packages Within D Days — the lesson's check, by days.
- Split Array Largest Sum — the figure's problem.
- Magnetic Force Between Two Balls — maximise the minimum.
- Minimum Number of Days to Make m Bouquets — search over days.
Common questions
How do I know if binary search on the answer applies?
Look for "minimise the maximum" or "maximise the minimum" in the statement, and ask whether a bigger (or smaller) answer only makes the check easier. If raising the limit can never turn a yes into a no, the predicate is monotone and the search works. If you cannot write a fast yes/no check for a fixed guess, it does not help.
What should lo and hi be in binary search on the answer?
lo must be a value that is certainly feasible or certainly the boundary from below, and hi one you can prove is feasible. For splitting an array, lo is the largest element and hi the total sum. A wrong bound silently returns a wrong answer, so derive both from the statement's limits.
Why does my binary search loop forever?
Usually because mid rounds the wrong way for the update. With hi = mid and lo = mid + 1 use mid = lo + (hi - lo) / 2; with lo = mid and hi = mid - 1 use mid = lo + (hi - lo + 1) / 2. Otherwise a two-element range never shrinks.
How many iterations does binary search on the answer take?
About log2 of the range's width. A range up to 10^9 needs 30 checks and one up to 10^18 needs 60, so even an O(n) check over 10^5 elements costs only a few million operations in total.
Exercises
Split the array into k parts
Split an array of n positive integers into k non-empty contiguous parts so that the largest part sum is as small as possible. Print that smallest possible largest sum.
Input: n k (1 ≤ k ≤ n ≤ 10^5), then n integers a_i (1 ≤ a_i ≤ 10^9). Output: one integer.
5 2
7 2 5 10 8prints
18[7, 2, 5] and [10, 8] have sums 14 and 18; no split has a smaller maximum. Sums reach 10¹⁴, and the hidden cases are at the limits.
Aggressive cows
There are n stalls at distinct positions on a line and c cows. Put the cows in c different stalls so that the smallest distance between any two cows is as large as possible. Print that distance.
Input: n c (2 ≤ c ≤ n ≤ 10^5), then n distinct positions x_i (0 ≤ x_i ≤ 10^9), in any order. Output: one integer.
5 3
1 2 8 4 9prints
3Cows at 1, 4 and 8 (or 9) are at least 3 apart; no placement does better.
In this module: Binary search on the answer
← Checkpoint — Bit manipulation · Checkpoint — Binary search on the answer →