Problem context and objectives
Signal rescue operator · A beacon is hidden inside an ordered frequency band
Lock onto the signal without testing every frequency: The Split Peak Signal.
Each probe costs precious time; searching the wrong half moves the rescue team farther away.
How you win
- 1Recognize when Exact binary search matches the clues
- 2Keep this true after every move: if the target exists, it remains inside the inclusive interval from left through right
- 3Reach the result within O(log n)
Rules and pressure
- Target cost: O(log n)
- State rule: if the target exists, it remains inside the inclusive interval from left through right
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.
Predict the returned index. For a missing target, watch the boundaries cross. Lesson questions refer to the original example.
Live algorithm trace
Binary search: shrinking candidate interval
Complete executionLive indices: 0, 1, 2, 3, 4, 5, 6. Short blocks are discarded candidates.
The inclusive interval [0, 6] contains every possible target position.
left, right = 0, len(nums) - 1while left <= right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 else: return midreturn -1Truth to preserve / Cost target
If the target exists, its index stays inside [left, right]. Every unsuccessful comparison removes mid and at least half the remaining candidates.
O(log(n + 1)) comparisons and O(1) auxiliary space
Use sorted values to prove an entire half impossible. Short blocks show eliminated candidates.