Search a 2D Matrix
Search a 2D Matrix: each row is sorted, and the first value of each row exceeds the last of the previous row. Decide whether target exists in O(log(m·n)).
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -10⁴ <= matrix[i][j], target <= 10⁴
Intuition
Search a 2d matrix looks for a target in a matrix with two guarantees: each row is sorted ascending, and the first element of each row exceeds the last element of the previous row.
That second guarantee is the one that matters. It means reading the matrix row by row produces one fully sorted sequence:
- The matrix is a sorted array that has been folded into rows, so a single binary search over all m × n positions works directly.
Treating index i as row i / n and column i % n maps a flat position onto the matrix, and ordinary binary search proceeds without any special handling.
The integer division and modulo must use the column count, not the row count. Swapping them produces a mapping that looks reasonable and silently searches the wrong cells.
The two-stage alternative binary searches the first column to find the candidate row, then searches within it. Same O(log(mn)) total, since log m + log n equals log(mn), but with two loops to get right instead of one.
The staircase search from the top-right corner — moving left when too large, down when too small — is O(m + n). That is worse here, and it is the right technique for Search a 2D Matrix II, where rows and columns are sorted but the strong row-to-row guarantee does not hold.
Knowing which of the two problems you are looking at is the real test. This one's guarantee permits O(log(mn)); the other's does not.
One binary search gives O(log(mn)) time and O(1) space.
Row-sorted plus each row starting after the previous row ends means the matrix is one sorted array, just folded. Index mid maps back with divmod(mid, cols). Whenever a 2D structure is globally ordered, flatten the index rather than writing a two-stage search.
Approach
Before reading on: price up what sorting first costs here, then ask what property lets you throw away half the range after one comparison. Aim for O(log(m·n)) time and O(1) space.
Use the row-to-row guarantee
Each row's first element exceeds the previous row's last, so reading row by row yields one fully sorted sequence — the matrix is a folded sorted array.
Binary search the flat range
Search indices 0 to m × n − 1 as if the matrix were one array. No special handling of row boundaries is needed.
Map index to cell
Index i is row i / n, column i % n. Both must use the column count — swapping in the row count silently searches the wrong cells.
Know the two-stage alternative
Binary search the first column for the row, then within it. Same O(log(mn)), since log m + log n = log(mn), but two loops to get right.
Distinguish it from the sequel
Search a 2D Matrix II lacks the row-to-row guarantee and needs the O(m + n) staircase from the top-right corner. Identifying which problem you have is the real test.
Cost of the search
One binary search over m × n positions gives O(log(mn)) time and O(1) space.
Solution & live demo
Common pitfalls
Dividing by rows instead of cols
v = matrix[mid // rows][mid % rows]
v = matrix[mid // cols][mid % cols]
The flattened index advances one column at a time, so the row is mid / cols and the column is mid % cols. Using rows coincidentally works on square matrices and fails everywhere else — a nasty bug to catch by testing.
Setting hi to rows * cols
lo, hi = 0, rows * cols
lo, hi = 0, rows * cols - 1
With an inclusive while lo <= hi loop, hi must be the last valid index. Using the count instead reads one past the end on the first probe of a matching target.
Searching the row then the column separately
row = binary search for the right row return binary search in matrix[row]
lo, hi = 0, rows * cols - 1
Two searches are correct here but more code and more boundary conditions for the same O(log(m·n)). The flattened form is a single standard binary search — and it's the version that still works when you're asked for the k-th smallest element.
Edge cases
hi is pushed below lo without a match; the loop ends returning false.
The range is [0,0]; one comparison decides the answer.
Row boundaries are invisible to the flat index, so a value falling in a gap simply never equals target.