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 Matrix Staircase.
Each probe costs precious time; searching the wrong half moves the rescue team farther away.
How you win
- 1Recognize when Binary search on a virtual matrix matches the clues
- 2Keep this true after every move: if the target exists, its virtual flat index remains in the live interval
- 3Reach the result within O(log(rows times cols))
Rules and pressure
- Target cost: O(log(rows times cols))
- State rule: if the target exists, its virtual flat index remains in the live interval
Lesson 1 of 3
Do not copy the matrix into a flat array. Choose a flat index, then use division and remainder to address that exact cell.
Your call · Where is flat index 5 in a four-column matrix?