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.
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
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.