Binary search — advanced problems (on the answer)

When the answer is an integer and feasibility is monotone, binary search the answer and verify each guess with a short greedy loop.

Binary search on the answer

You guess a candidate answer mid and run check(mid) that returns true/false. If larger answers are always easier (or always harder), the truth values are monotone and you can binary search smallest or largest feasible value.

Contest recipe: prove monotonicity on paper, code check first, then wrap a loop with clear lo / hi meaning.

Problem 1 — Split array: minimize largest subarray sum

Task: Split a into at most m contiguous parts. Minimize the maximum sum among those parts.

Idea: If max sum ≤ cap is possible, then any larger cap is also possible — search the smallest good cap. check(cap): greedily pack elements into the current part until adding the next would exceed cap; then start a new part. If any single element exceeds cap, impossible.

Explanation: Greedy packing is optimal for a fixed cap because earlier parts should be as full as possible without breaking the limit.

Solution 1 — code

#include <bits/stdc++.h>
using namespace std;

bool check(const vector<int>& a, int m, long long cap) {
    int parts = 1;
    long long sum = 0;
    for (int x : a) {
        if (x > cap) return false;
        if (sum + x > cap) {
            parts++;
            sum = x;
        } else sum += x;
    }
    return parts <= m;
}

int main() {
    vector<int> a = {7, 2, 5, 10, 8};
    int m = 2;
    long long lo = 0, hi = 0;
    for (int x : a) hi += x;
    while (hi - lo > 1) {
        long long mid = lo + (hi - lo) / 2;
        if (check(a, m, mid)) hi = mid;
        else lo = mid;
    }
    cout << hi << "\n";
    return 0;
}

Problem 2 — Minimum eating speed

Task: piles[i] bananas in pile i. You eat k bananas per hour from one pile (ceil division). Find minimum k so that everything finishes within H hours.

Idea: Larger k only helps — check(k) is monotone. check(k): sum ceil(piles[i] / k) and compare to H.

Explanation: If speed k works, any faster speed works; binary search smallest k from 1 to max(piles).

Solution 2 — code

#include <bits/stdc++.h>
using namespace std;

bool check(const vector<int>& piles, int H, int k) {
    long long h = 0;
    for (int p : piles) {
        h += (p + k - 1) / k;
        if (h > H) return false;
    }
    return true;
}

int main() {
    vector<int> piles = {3, 6, 7, 11};
    int H = 8;
    int lo = 0, hi = *max_element(piles.begin(), piles.end()) + 1;
    while (hi - lo > 1) {
        int mid = lo + (hi - lo) / 2;
        if (check(piles, H, mid)) hi = mid;
        else lo = mid;
    }
    cout << hi << "\n";
    return 0;
}

Problem 3 — Aggressive cows (maximize minimum distance)

Task: Sorted stall positions x[]. Place c cows in distinct stalls. Maximize the minimum distance between any two cows.

Idea: If minimum distance ≥ d is possible, then ≥ d-1 is also possible — search largest good d. check(d): put first cow in first stall; each next cow goes to the first stall at least d away from the last placed cow. Count cows.

Explanation: Greedy placement is correct for a fixed d: always leave the earliest stall free only if you must; skipping forward never hurts feasibility.

Solution 3 — code

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    vector<int> x = {1, 2, 4, 8, 9};
    int c = 3;
    int lo = 0, hi = x.back() - x.front() + 1;
    while (hi - lo > 1) {
        int mid = lo + (hi - lo) / 2;
        if (check(x, c, mid)) lo = mid;
        else hi = mid;
    }
    cout << lo << "\n";
    return 0;
}

Template

Implement check first; keep lo bad / hi good (or the reverse) and shrink until adjacent.

1lo = known infeasible (or 0)
2hi = known feasible (or max answer + 1)
3while hi - lo > 1
4  mid = lo + (hi - lo) / 2
5  if check(mid) then hi = mid   // or lo = mid for "maximize" variant
6  else lo = mid
7answer = hi   // adjust to lo/hi convention you chose

Complexity

O(n log U) is typical: log U iterations from the answer range, O(n) per check for these three problems.

Complexity Analysis

Time Complexity

O(n log U) with U = answer range (sum, max pile, or coordinate span)

Space Complexity

O(1) extra besides the input

Growth Rate Comparison

Binary Search