Binary search on the answer

Sometimes there is no sorted array to search, but the answer is a number in a known range: the minimum speed, the smallest capacity, the largest minimum distance. If you can write a function feasible(x) that says yes or no, and the answers look like no, no, no, yes, yes, yes as x grows (monotonic), then the smallest feasible x can be found by binary search.

The cost is the number of halvings, about log2 of the range size, times the cost of one feasibility check. A range of 1 to 1,000,000,000 needs only about 30 checks. The skill is in recognising the pattern and writing a correct greedy check.

1. 1Identify the answer variable x and its possible range [lo, hi]. For example, eating speed is between 1 and the largest pile.
2. 2Write feasible(x): can the task be done with value x? It is usually a simple greedy pass over the input in O(n).
3. 3Check monotonicity: if x works, does every larger x also work (or every smaller x, for maximise problems)? If not, binary search does not apply.
4. 4Search for the first feasible x: while lo < hi, mid = (lo + hi) // 2; if feasible(mid) then hi = mid else lo = mid + 1. The answer is lo.
5. 5For 'maximise the minimum' problems the predicate flips the other way (yes, yes, no, no); search for the last yes with mid = (lo + hi + 1) // 2, lo = mid on yes and hi = mid - 1 on no, so the loop always moves.
6. 6Total time is O(cost of feasible x log(hi - lo)).

def min_eating_speed(piles, h):
    """Smallest speed k (bananas per hour) that finishes all piles within h hours."""
    def hours_needed(k):
        return sum((p + k - 1) // k for p in piles)   # ceil(p / k) per pile

    lo, hi = 1, max(piles)             # the answer is somewhere in [1, max pile]
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(mid) <= h:     # feasible: try to go slower
            hi = mid
        else:                          # too slow: must eat faster
            lo = mid + 1
    return lo                          # lo == hi == smallest feasible speed

hours_needed is the feasibility check, O(n). Faster speeds never need more hours, so feasibility flips once from false to true, and the first-true template finds the minimum. (p + k - 1) // k is integer ceiling. Total time O(n log M) where M is the largest pile; space O(1).

Cost: O(C x log R) where C is the cost of one feasibility check and R is the size of the answer range; usually O(n log R) with O(1) extra space.