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 Rotated Pass.
Each probe costs precious time; searching the wrong half moves the rescue team farther away.
How you win
- 1Recognize when Search in a rotated sorted array matches the clues
- 2Keep this true after every move: if the target exists, it remains within the live interval
- 3Reach the result within O(log n)
Rules and pressure
- Target cost: O(log n)
- State rule: if the target exists, it remains within the live interval
New words in this mission
Open a term for a plain-language explanation.O(log n)+
The work grows by one step when the input roughly doubles. Binary search achieves this by discarding half of the remaining search space each time.
Lesson 1 of 3
At every midpoint, at least one half is sorted by value. Identify it first, then decide whether the target lies within its endpoint range.
Your call · For [4,5,6,7,0,1,2], mid=7 and target=0, which half is sorted?