Optimization -> Decision: Binary Search on the Answer

Quick Revisit

• USE WHEN: "minimize/maximize X" where feasibility check is monotone (once achievable, stays achievable)
• INVARIANT: check(T) is monotone — true for all T ≥ T* (min) or T ≤ T* (max)
• TIME: O(log(range) × C) where C = cost of one feasibility check | SPACE: O(1) + check space
• CLASSIC BUG: wrong binary search boundaries or off-by-one — for float answers, use fixed iteration count
• PRACTICE: 08-ladder-mixed

Every optimization problem hides a decision problem. "Find the minimum $X$" becomes "Can we achieve $X$?" If you can answer the decision version efficiently, binary search gives you the optimization for free.

Difficulty: [Intermediate]CF Rating Range: 1400-2000 Prerequisites: Binary Search

Contents

• The Meta-Pattern
• When It Works: Monotonicity
• Six Detailed Examples
• When It Fails
• Implementation Notes
• Practice Problems

---

The Meta-Pattern

The transformation has three parts:

1. Original problem: "Minimize $f(\text{arrangement})$" or "Maximize $g(\text{arrangement})$."
2. Decision version: "Is $f(\text{arrangement})\le T$ achievable?" for a threshold $T$.
3. Binary search on $T$: run the decision check for each candidate $T$. Narrow the search range until you've found the optimal value.

                    ┌─────────────────────────┐
  Optimization      │  Binary search over T   │      Decision
  "minimize X"  ──► │  lo=0, hi=MAX           │ ──►  "is X <= T possible?"
                    │  while lo < hi:          │
                    │    mid = (lo+hi)/2       │       check(mid)
                    │    if check(mid): hi=mid │        │
                    │    else: lo=mid+1        │       true/false
                    └─────────────────────────┘

Total complexity: $O(\log (\text{range})\times C)$ where $C$ is the cost of one call to check(T).

When It Works: Monotonicity

The critical requirement is monotonicity of the predicate:

• For minimization: if check(T) returns true (achievable for threshold $T$), then check(T') must also return true for all $T^{\prime }>T$.
• For maximization: if check(T) is true, then check(T') is true for all $T^{\prime }<T$.

In other words, the set of feasible thresholds forms a contiguous suffix (or prefix) of the search space. Binary search finds the boundary.

Why it's usually satisfied: most "minimize the maximum" or "maximize the minimum" problems have this property because relaxing the threshold only makes the constraint easier to satisfy.

Six Detailed Examples

1. Splitting Tasks (in Order) Across $k$ Workers

Problem. $n$ tasks with processing times $d_1,\dots ,d_n$, given in a fixed order. You must split them into $k$ contiguous prefixes (worker $j$ takes a contiguous block of consecutive tasks) and minimize the maximum total time on any worker. This is the standard "painter's partition" / "split array largest sum" formulation.

Decision version. "Can we split the array into $\le k$ contiguous blocks, each with sum $\le T$?"

Check function. Greedy in-order packing: scan once, accumulate into the current block, start a new block whenever adding the next task would exceed $T$.

bool check(long long T, vector<int>& tasks, int k) {
    int blocks = 1;
    long long cur_load = 0;
    for (int d : tasks) {
        if (d > T) return false;            // single task too large
        if (cur_load + d <= T) cur_load += d;
        else { blocks++; cur_load = d; }
    }
    return blocks <= k;
}

Binary search range: $[max(d_i),\sum d_i]$. Total: $O(n\log (\text{sum}))$.

Why this is the contiguous version, not the general one. The greedy above is correct only because tasks are split in order (each worker gets a prefix-block). The harder problem — "$k$ identical machines, each task can go on any machine, minimize makespan" — is bin-packing-flavored and NP-hard. There is no polynomial greedy check for it; you would need PTAS / LPT heuristics or DP for small $k$. If a problem allows arbitrary task-to-machine assignment, the binary-search-plus-greedy template here is wrong.

2. Maximum Minimum Distance (Aggressive Cows)

Problem: $n$ stalls at positions $x_1<x_2<\cdots <x_n$. Place $k$ cows so that the minimum distance between any two cows is maximized.

Decision version: "Can we place $k$ cows such that all pairwise distances $\ge D$?"

Check function (greedy placement): place the first cow at $x_1$. For each subsequent stall, place a cow if its distance from the last placed cow is $\ge D$. Count placed cows.

bool check(int D, vector<int>& x, int k) {
    int placed = 1, last = x[0];
    for (int i = 1; i < (int)x.size(); i++) {
        if (x[i] - last >= D) { placed++; last = x[i]; }
    }
    return placed >= k;
}

Search range: $[1,x_{n-1}-x_0]$. Monotonic because: if we can space cows $\ge D$ apart, we can certainly space them $\ge D-1$ apart.

3. Minimum Maximum Pages Per Worker

Problem: $n$ books with page counts in order. Divide into $k$ contiguous segments. Minimize the maximum total pages in any segment.

Decision version: "Can $k$ workers handle it with maximum $P$ pages each?"

Check function (greedy assignment): scan left to right, accumulating pages. When the running sum exceeds $P$, start a new worker.

bool check(long long P, vector<int>& pages, int k) {
    int workers = 1;
    long long cur = 0;
    for (int p : pages) {
        if (p > P) return false;  // single book exceeds limit
        if (cur + p > P) { workers++; cur = p; }
        else cur += p;
    }
    return workers <= k;
}

Classic "painter's partition" / "split array largest sum" problem.

4. K-th Smallest Element in a Sorted Matrix

Problem: $n\times n$ matrix where each row and each column is sorted. Find the $k$-th smallest element.

Decision version: "How many elements $\le X$?"

Check function: for each row, binary search (or use the sorted-column property to do a staircase walk) to count elements $\le X$. If the count is $\ge k$, then the $k$-th smallest is $\le X$.

int countLeq(vector<vector<int>>& mat, int X) {
    int n = mat.size(), cnt = 0;
    int col = n - 1;
    for (int row = 0; row < n; row++) {
        while (col >= 0 && mat[row][col] > X) col--;
        cnt += col + 1;
    }
    return cnt;
}

Binary search range: $[\text{mat}[0][0],\text{mat}[n-1][n-1]]$. Total: $O(n\log (\text{value range}))$.

5. Minimum Cost to Cut Array into K Pieces (DP Check)

Problem: cut an array into exactly $k$ pieces, minimizing the maximum piece sum. Sometimes the check function isn't greedy -- it requires DP.

Decision version: "Can we partition into $k$ pieces where each piece sum $\le C$?"

For simple contiguous partitions, a greedy check works (same as example 3). But in harder variants (e.g., with additional constraints on piece structure), the check may need a DP that runs in $O(n)$ or $O(n\log n)$ per call.

The outer binary search contributes only a $\log$ factor, so even an $O(n\log n)$ check yields $O(n\log n\log V)$ overall -- still fast.

6. Parallel Binary Search: Many Queries Offline

Problem: $m$ queries, each asking "find the threshold for query $i$." Processing them independently costs $O(m\log V\cdot C)$. Parallel binary search processes all queries simultaneously in $O(\log V\cdot (n+m))$ total.

Idea: maintain an interval $[{\text{lo}}_i,{\text{hi}}_i]$ for each query. In each "round," group queries by their midpoint, sweep through the data once, and update all intervals. After $O(\log V)$ rounds, all queries are answered.

This technique is essential for problems like "for each element, find the earliest time it satisfies condition $X$," where the data evolves over time and re-scanning per query is too expensive.

When It Fails

Binary search on the answer requires monotonicity. Watch out for:

• Non-monotonic predicates. "Can we partition into $k$ pieces with each piece sum exactly equal to $T$?" Being achievable for $T$ doesn't imply achievable for $T+1$. Binary search doesn't apply.
• Discrete answer spaces with gaps. If the answer can only be certain scattered values (e.g., specific primes), binary search on a continuous range may land between valid answers. You may need to search over the discrete candidates directly.
• Floating-point answers. Binary search still works, but you must be careful with precision. Use a fixed number of iterations (e.g., 100) rather than while (hi - lo > eps), which can loop forever for very small eps.

Implementation Notes

This topic is as much about avoiding off-by-one bugs as it is about recognizing monotonicity. Memorize one template per direction and never deviate.

Integer template: minimize $T$ subject to check(T)

Invariant. Throughout the loop, the answer lies in $[\text{lo},\text{hi}]$. check(\text{hi}) is always true; check(\text{lo} - 1) is always false (or lo starts at the global minimum).

long long lo = LO_MIN, hi = HI_MAX;       // hi must satisfy check(hi)
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;   // round down
    if (check(mid)) hi = mid;             // shrink upper bound
    else            lo = mid + 1;         // mid impossible, exclude it
}
// lo == hi == smallest T with check(T) == true

Three things to verify before trusting the answer:

1. The initial hi is feasible — i.e., check(hi) returns true. If not, the loop returns garbage. Always set hi to a safe upper bound (sum of all elements, large enough constant, etc.).
2. mid = lo + (hi - lo) / 2 rather than (lo + hi) / 2 to avoid overflow on near-LLONG_MAX ranges.
3. The loop condition is lo < hi (strict). If you write lo <= hi, you'll need a different update pattern and a separate ans variable.

Integer template: maximize $T$ subject to check(T)

Mirror image: lo is always feasible, hi is the smallest infeasible.

long long lo = LO_MIN, hi = HI_MAX;       // lo must satisfy check(lo)
while (lo < hi) {
    long long mid = lo + (hi - lo + 1) / 2;   // round UP
    if (check(mid)) lo = mid;                 // mid feasible, push up
    else            hi = mid - 1;             // mid infeasible
}
// lo == hi == largest T with check(T) == true

The rounding direction is the only difference from the minimization template. Round up so mid > lo whenever lo + 1 < hi; otherwise the loop never advances.

Floating-point template

double lo = LO_MIN, hi = HI_MAX;
for (int iter = 0; iter < 200; iter++) {     // 200 iters >> log2(1e18)
    double mid = (lo + hi) / 2;
    if (check(mid)) hi = mid;                // (or lo = mid for max)
    else            lo = mid;
}
double ans = lo;                             // lo and hi are within 2^-200

Use a fixed iteration count rather than while (hi - lo > eps) — floating-point underflow can make the loop run forever. 100 iterations already gets you below ${10}^{-30}$ relative error from a ${10}^{18}$ range.

Practice Problems

Problem	Pattern	Source
CF 460C -- Present	Binary search + greedy range check	CF
CF 551C -- GukiZ hates Boxes	Binary search on time + greedy simulation	CF
CF 1223D -- Equalizing by Division	Binary search on answer + multiset check	CF
SPOJ AGGRCOW	Maximum minimum distance (classic)	SPOJ
LC 410 -- Split Array Largest Sum	Painter's partition	LeetCode

---

See also: Binary Search for the core technique and edge-case handling. Binary search on the answer is arguably the most common "upgrade" that takes a 1500-rated solver to 1700+.