Binary Search on the Answer

Concepts: pyBinarySearchAnswer, pyFeasibilityFunction

This is the most important intermediate binary search concept. The insight: instead of searching for a value in an array, you binary search on the range of possible answer values. You define a feasibility function is_feasible(x) that returns True if answer x is achievable and False if it is not. The function must be monotonic: if x is feasible, then everything easier than x is also feasible. Binary search finds the minimum x such that is_feasible(x) is True. Template: Binary Search on the Answer Example 1: Koko Eating Bananas (LeetCode 875) Koko has piles of bananas and H hours. She eats at speed K bananas/hour (one pile per hour). Find minimum K. The answer range is [1, max(piles)]. Feasibility check: can she eat all piles in H hours at speed K? O(n) check. Binary search the answer range.