Binary search on the answer

O(n log(range))

Binary search a range of possible answers instead of an array index: guess a value, run an O(n) feasibility check, and shrink the range based on whether the guess works.

Signals

minimize the maximum / maximize the minimumsmallest value that satisfies a conditionfind the smallest capacity/speed/days that worksanswer lies in a numeric range, not an array positiona feasibility check is monotonic (true after some point)

Template

function smallestFeasible(lo, hi, canDo) {
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (canDo(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// canDo(x) must be monotonic: false...false, true...true

Looks similar, isn't

Binary search (array): Array binary search finds a value that's already sitting in a sorted array. Here there's no array to index into; you binary search over a range of possible ANSWERS and test each guess with a separate feasibility function.

answer range up to ~1e9, an O(n) check per guess, monotonic feasibility -> O(n log(range)) time. 'Minimize the maximum' or 'smallest x that works' over a huge range is the cue, not the array size itself.

Learn this pattern