uniolympiads Ελληνικά

Binary search on the answer

When "is it possible with xx?" is monotone in xx, you find the smallest feasible xx in O(log⁡)O(\log) checks.

When

The problem asks for "the smallest xx such that…" or "the largest xx such that…", and it is easy to check whether a given xx is enough. The signal is monotonicity: if xx is enough, so is every larger value.

The idea

Let ok(x)\mathrm{ok}(x) be false, …, false, true, …, true on [lo,hi][lo, hi]. Keep the invariant: everything below lolo is false, everything above hihi is true. Each step looks at the middle and discards half of the range. After ⌈log⁡2(hi−lo+2)⌉\lceil \log_2(hi - lo + 2) \rceil steps the answer is left.

In Factory Machines, ok(t)\mathrm{ok}(t) is "in time tt the machines make at least kk products", that is ∑i⌊t/ki⌋≥k\sum_i \lfloor t / k_i \rfloor \ge k. This is monotone in tt and takes O(n)O(n) to compute.

Pitfalls

  • (lo + hi) / 2 overflows when the bounds are near 101810^{18}. lo + (hi - lo) / 2 does not.
  • The upper bound must certainly be feasible. In Factory Machines it is k⋅min⁡ikik \cdot \min_i k_i, up to 101810^{18}: it fits in long long, but the sum inside ok\mathrm{ok} can go past it. Stop as soon as it reaches kk.
  • Write ok\mathrm{ok} 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.

cpp/binary-search.cpp
// 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.

More in the USACO Guide

In English, with more problems per level.