Binary Search on the Answer
MediumKoko eating bananas. The array is not sorted, but feasibility is monotonic in the eating speed, so binary search the speed instead of the array.
monotonic predicatefeasibility check
TimeO(n log maxPile)
SpaceO(1)
Inputpile sizes | hours available
30
0
11
1
23
2
4
3
20
4
Piles: 30, 11, 23, 4, 20. You have 6 hours. Find the slowest speed that still finishes.
checks0
1 / 12
lo = 1; hi = max(piles)
while lo < hi:
mid = (lo + hi) / 2
if hoursNeeded(mid) <= H: hi = mid
else: lo = mid + 1
return lo
Why it matters
The pattern behind minimise the maximum and maximise the minimum problems.
Practise this
Keyboard
space play← → stepr restartctrl K search
More in Binary Search
Next visualiser
Two Pointers