Binary Search on the Answer

Foundations

So far, binary search ran over the indexes of an array. Now, what if there is no array to search, only a range of possible answers and a way to test whether one of them works?

Binary search on the answer needs a monotonic check: a yes-or-no question whose answers flip exactly once as the candidate grows, such as fail, fail, pass, pass. Search the candidates from lo to hi as before: if mid passes, it might be the answer and nothing larger is needed, so hi = mid; if it fails, lo = mid + 1. When lo == hi, that candidate is the smallest one that passes.

On nums = [7, 1, 5, 3, 6], find the smallest x with at least 3 elements <= x. That count only grows with x, so the checks fail, then pass. Over candidates 1 to 7: x = 4 counts 2 and fails, so lo = 5; x = 6 counts 4 and passes, so hi = 6; x = 5 counts 3 and passes, so hi = 5. Now lo == hi: the answer is 5.

Case Scenario

Koko Eating Bananas searches on the answer: piles of bananas, piles[i], must be eaten within h hours at k bananas per hour, one pile at a time. A pile p takes ceil(p / k) hours, and a faster speed never takes longer, so the check is monotonic. For piles = [3, 6, 7, 11] and h = 8, the smallest speed that fits is 4.

The direct approach tries every speed from 1 upward until the hours fit. Each check sums ceil(p / k) over all n piles, and the answer can be as large as the biggest pile, m, so the search costs O(n · m). With piles in the billions, that is billions of checks, though the yes-or-no answers only flip once.