AlgoScope

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.

Problem-solving patterns, pattern, intermediate
Capacity 32 needs 2 days, feasible.102132435465768798109
Capacity 32 needs 2 days, feasible.102132435465768798109

Search on the Answer: Least ship capacity in 5 days

Decision, step 2 of 7

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)