Binary Search on Answer Space

Sometimes the problem asks for the minimum or maximum value of something (capacity, threshold, distance) that satisfies a condition. If “is value X enough?” can be answered in O(n) or O(n log n), and the answer is monotonic (if X works, then X+1 works too, or the opposite), you can binary search on the answer space.

When to Use

  • Problem asks for min or max of a parameter (e.g. min capacity, max distance, min threshold).
  • You can write a predicate possible(x) that returns true if x is feasible.
  • Feasibility is monotonic: e.g. if possible(5) is true then possible(6) is true (or the reverse).

Template

Java
int low = minPossibleValue, high = maxPossibleValue;
while (low <= high) {
    int mid = low + (high - low) / 2;
    if (possible(mid)) {
        // Try smaller (for min) or larger (for max)
        answer = mid;
        high = mid - 1;  // for min answer
        // low = mid + 1;  // for max answer
    } else {
        low = mid + 1;   // for min answer
        // high = mid - 1; // for max answer
    }
}
return answer;

Example: Capacity to Ship Within D Days

Given weights and days D, find the minimum capacity so all packages can be shipped in at most D days.

  • Answer space: capacity from max(weights) to sum(weights).
  • possible(cap): can we ship all in ≤ D days with capacity cap? (Greedy: fill days until cap is exceeded.) Monotonic: if cap works, larger cap works.
  • Binary search for the smallest cap such that possible(cap) is true.

Summary

Binary search on the answer: define the range, implement possible(x), and binary search for the minimum (or maximum) feasible value. Time is O(log(range)) × cost of possible(x).