Binary search on the answer — what does it mean? When does it apply?

Problem. What does "binary search on the answer" (parametric search) mean, and how do you recognize when it applies?

The shift in mindset

Ordinary binary search looks for a value in a sorted array. Binary search on the answer drops the array entirely: you search a range of candidate answers for the threshold where a monotonic feasibility predicate flips. You never sort or store the inputs — you guess an answer and ask "is this achievable?"

candidate x:  small ........................ large
feasible(x): F   F   F   F   T   T   T   T   T
                           ^ first feasible answer (the optimum)

The three conditions

1. The answer lives in a numeric range [lo, hi] you can bound (a speed, a capacity, a maximum allowed sum).
2. There's a feasible(x) test you can evaluate, usually in O(n).
3. feasible is monotonic — if x works, every larger (or every smaller) x works too. That F…F T…T step is what makes the boundary binary-searchable.

If those hold, binary-search the boundary in O(log(range) × cost(feasible)).

int searchAnswer(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;   // mid works -> answer is mid or smaller
        else lo = mid + 1;             // mid fails -> need something larger
    }
    return lo;                          // first feasible value
}

Recognizing it

The tells: a problem asks for the minimum capacity / maximum value / smallest speed such that some constraint holds, and a brute-force "try every candidate" would be linear or worse over the range. Examples: Koko Eating Bananas (search eating speed; feasible = finishes in time), Capacity to Ship Packages in D Days (search capacity; feasible = fits in D days), Split Array Largest Sum, and Minimize Max Distance to Gas Station.