Problem context and objectives
Mission briefing
Signal rescue operator · A beacon is hidden inside an ordered frequency band
Lock onto the signal without testing every frequency: The Banana Clock.
Each probe costs precious time; searching the wrong half moves the rescue team farther away.
How you win
- 1Recognize when Binary search on answer matches the clues
- 2Keep this true after every move: all speeds below left are infeasible and right remains a feasible candidate
- 3Reach the result within O(n log max pile)
Rules and pressure
- Target cost: O(n log max pile)
- State rule: all speeds below left are infeasible and right remains a feasible candidate
Lesson 1 of 3
Live algorithm trace
Binary search on answer
Complete execution1 of 8
Speed 11 is certainly feasible because each pile takes at most one hour.
1
left, right = 1, max(piles)2
speed = midpoint3
hours = sum(ceil(pile / speed))4
if hours <= h: right = speed5
otherwise left = speed + 16
return lefth = 8left = 1right = 11
Truth to preserve / Cost target
Truth to preserve
all speeds below left are infeasible and right remains a feasible candidate
Cost target
O(n log max pile)
The candidate speed is not stored in an array, but feasibility is monotonic: once a speed finishes in time, every faster speed also works. Search the first feasible integer speed.
Your call · What should guide every step of this algorithm?