Searching Sorted Matrices

Two common sorted-matrix layouts come up. The right algorithm depends on which one.

Strictly sorted (row-major)

Each row is sorted, and the first value of each row is greater than the last of the previous. Effectively a sorted array laid out in 2D. Treat it as a 1D sorted array of length $m \cdot n$ and binary-search; map flat index $i$ to row $i / n$, column $i \mod n$. $O(\log(mn))$.

Row-sorted and column-sorted (each independently)

Each row is sorted left to right, and each column is sorted top to bottom — but rows aren't ordered relative to each other. Start at the top-right corner. If the value is the target, done. If the value is greater than the target, move left (the rest of this row is too big). If less, move down (the rest of this column is too small). At most $m + n$ steps. $O(m + n)$.

Why the corner trick works

The top-right (or bottom-left) corner is the only position where exactly one direction makes the value larger and the other makes it smaller. From there, every step eliminates one row or one column. This won't work from the top-left or bottom-right corners — both adjacent moves go the same way.

Variants

"Count elements less than X" — same stairstep approach. "K-th smallest element in a sorted matrix" — combine a min-heap with stairstep search, or binary-search on the answer.

What NOT to do

Don't binary search row by row — that's $O(m \log n)$, worse than $O(m + n)$ for typical sizes. The 2D structure is more constrained than $m$ independent sorted rows; exploit it.