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 First True Beacon.
Each probe costs precious time; searching the wrong half moves the rescue team farther away.
How you win
- 1Recognize when First-true boundary template matches the clues
- 2Keep this true after every move: all indices before left are proven false and right is the earliest remaining true candidate
- 3Reach the result within O(log n)
Rules and pressure
- Target cost: O(log n)
- State rule: all indices before left are proven false and right is the earliest remaining true candidate
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 result first. With no true value, the search reaches n and returns -1. Lesson questions refer to the original example.
Live algorithm trace
First true: locate the transition
Complete executionLive indices: 0, 1, 2, 3, 4, 5. Short blocks are discarded candidates.
F means false and T means true. Search [0, 6); position 6 is a sentinel for no true value, never a cell to read.
left, right = 0, len(flags)while left < right: mid = left + (right - left) // 2 if flags[mid]: right = mid else: left = mid + 1return left if left < len(flags) else -1Truth to preserve / Cost target
Every position before left is false. If right<n, right is true and remains a possible answer.
O(log(n+1)) predicate checks and O(1) auxiliary space
Finding true is not yet proof that it is the first true.