What does it solve?
Search for a target in a matrix with sorted structure. Matrix I: each row is sorted and every row's first value exceeds the previous row's last, so the whole thing is one sorted sequence. Matrix II: rows and columns are each sorted, but rows don't chain together.
Key insight: for I, map a 1-D index idx to cell (idx/cols, idx%cols) and binary search over rows·cols → O(log(mn)). For II, start at the top-right: bigger than target → move left, smaller → move down. Each step drops a row or column → O(m+n).
The core idea
Complexity
Matrix I · time
O(log mn)
Binary search over all m·n cells using the flat-index trick. O(1) space.
Matrix II · time
O(m + n)
The staircase walk eliminates one row or column per step from the top-right. O(1) space.
Examples & edge cases
Live animation
Matrix
Press Play to begin…
Current step detail
—
—
—
found = —
Step — of —
probe cell
—
value
target
—
searching for
search space
—
cells left
answer
—
found?
Select an example and press Play to start.
✓ Done
SpeedMedium
Step-by-step table
C++ implementation
search_2d.cpp
My Notes
📝Notes✅
Practice this problem