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)).
Intuition
Those two ordering rules mean the matrix, read row by row, is one fully sorted sequence. So we binary-search over the virtual index 0 … m·n−1 and convert each index to a (row, col) on the fly.
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
A linear scan ignores the sorting
Checking every cell is O(m·n) and throws away the strong guarantees we're given: each row is sorted, and every row starts higher than the previous row ends. Those two facts together mean the matrix has a hidden global order — and global order is what binary search exploits to reach O(log) time.
The matrix is one sorted array in disguise
Read row by row, the whole grid is a single ascending sequence of m·n values. So we can binary-search over a virtual index from 0 to m·n−1, never building the flat array. Any index mid converts back to a real cell in O(1): row = mid // cols, column = mid % cols. That conversion is the only new idea on top of a textbook binary search.
Standard binary search on the virtual range
Set lo = 0, hi = m·n − 1. Each step, take mid, map it to its cell value, and compare to target: equal means found; smaller means search the right half (lo = mid+1); larger means the left half (hi = mid−1). The row boundaries are invisible to the index, so a target that would fall 'between rows' simply never matches. O(log(m·n)) time, 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.