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 Insertion Gate.
Each probe costs precious time; searching the wrong half moves the rescue team farther away.
How you win
- 1Recognize when Lower-bound search matches the clues
- 2Keep this true after every move: every index before left is too small and every index at or after right is a valid insertion candidate
- 3Reach the result within O(log n)
Rules and pressure
- Target cost: O(log n)
- State rule: every index before left is too small and every index at or after right is a valid insertion 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 first qualifying position. Equality still searches earlier duplicates. The position after the array is also a valid answer. Lesson questions refer to the original example.
Live algorithm trace
Lower bound: keep the first qualifying position
Complete executionLive indices: 0, 1, 2, 3. Short blocks are discarded candidates.
Search cells in [0, 4). Position 4 after the array is also a possible insertion answer, not an array cell.
left, right = 0, len(nums)while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = midreturn leftTruth to preserve / Cost target
Every value before left is below target. The answer lies in [left, right], while inspected cells lie in [left, right).
O(log(n + 1)) comparisons and O(1) auxiliary space
Keep a qualifying midpoint as a possible answer.