Flat Binary Search vs Staircase Search
Check which sorting guarantee the problem gives you. If every row starts above the previous row's end, the matrix is one sorted sequence and binary search it in O(log mn). If rows and columns are each sorted independently, that fails and the staircase walk is the answer in O(m + n).
Two matrix search problems look identical and are not. In the stronger one, reading the matrix row by row gives a single sorted sequence, so the indices can be flattened and binary searched. In the weaker one each row and each column is sorted but a row does not continue where the previous one ended, so the flattened sequence is not sorted and binary search returns nonsense.
Side by side
| Dimension | Flat binary search | Staircase search |
|---|---|---|
| Requires | Every row starts above the previous row's end | Each row and each column sorted |
| Cost | O(log mn) | O(m + n) |
| Starting point | The middle of the flattened range | The top-right or bottom-left corner |
| What one step eliminates | Half the remaining cells | One whole row or one whole column |
| Index arithmetic | row = i / cols, col = i % cols | None, move one step at a time |
| Fails when | Rows restart below the previous maximum | Nothing, it is the general case |
When to pick each
Flat binary search
- The statement says the first integer of each row is greater than the last integer of the previous row.
- You need the position of an absent value, since the binary search tells you where it would be inserted.
Staircase search
- The statement says integers in each row are sorted and integers in each column are sorted, with no relationship between rows.
- Wide or tall matrices, where m + n is still much smaller than the number of cells.
- Kth smallest in a sorted matrix, which builds on the same corner-walking intuition.
Reading sorted matrix and reaching for the flattened binary search. On a matrix that is only row and column sorted the flattened sequence goes up and down, the comparison sends the search into the wrong half, and the answer is wrong rather than slow. Read the guarantee in the statement before choosing, because the two problems are told apart by one sentence.
Questions people ask
Why must the staircase walk start at a corner?
Because the top-right and bottom-left are the only cells where the two available moves do opposite things. From the top-right, going left strictly decreases and going down strictly increases, so one comparison always eliminates a whole row or column. From the top-left both moves increase, so no comparison rules anything out.
Is binary searching each row ever right?
Sometimes. It costs O(m log n), which beats O(m + n) when the matrix is tall and narrow and loses when it is wide. The staircase is the safer default because its bound does not depend on the shape, and it is the answer interviewers are listening for.
How do I convert a flat index back to row and column?
row = index / columns and column = index % columns, using integer division. The reverse is index = row * columns + column. Getting the two mixed up is the usual bug, and the quickest check is index 0 mapping to the top-left cell and the last index to the bottom-right.