Binary search on the answer
When "is it possible with ?" is monotone in , you find the smallest feasible in checks.
When
The problem asks for "the smallest such that…" or "the largest such that…", and it is easy to check whether a given is enough. The signal is monotonicity: if is enough, so is every larger value.
The idea
Let be false, …, false, true, …, true on . Keep the invariant: everything below is false, everything above is true. Each step looks at the middle and discards half of the range. After steps the answer is left.
In Factory Machines, is "in time the machines make at least products", that is . This is monotone in and takes to compute.
Pitfalls
(lo + hi) / 2overflows when the bounds are near .lo + (hi - lo) / 2does not.- The upper bound must certainly be feasible. In
Factory Machinesit is , up to : it fits inlong long, but the sum inside can go past it. Stop as soon as it reaches . - Write first and test it alone on two values. Most bugs are there, not in the loop.
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Binary search on a monotone predicate.
// ok(x) is false, false, ..., false, true, true, ... on [lo, hi].
// Returns the first x in [lo, hi] with ok(x) true, or hi + 1 if there is none.
// Invariant: everything below lo is false, everything above hi is true.
template <typename F>
ll firstTrue(ll lo, ll hi, F ok) {
ll answer = hi + 1;
while (lo <= hi) {
ll mid = lo + (hi - lo) / 2;
if (ok(mid)) {
answer = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return answer;
}
Tested on 5,001 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- Factory Machines · Sorting and Searching
- Array Division · Sorting and Searching
- Multiplication Table · Additional Problems I
More in the USACO Guide
- Binary Search · usaco.guide/silver/binary-search
In English, with more problems per level.