Binary Search on Answer
Recognize it when 'is x feasible?' is monotonic in x. Binary search the answer space with one feasibility check per probe.
Search on the Answer: Least ship capacity in 5 days
Range 10 to 55, probe capacity 32. Pack greedily, starting a new day whenever the next package would overflow: 1+2+3+4+5+6+7 | 8+9+10, 2 days. Within 5, so 32 works and anything bigger is unnecessary: hi = 32.
Cost
- Best
- O(log range * check)
- Average
- O(log range * check)
- Worst
- O(log range * check)
- Space
- O(1)