Search a 2D Matrix looks like a grid problem, but it is really binary search in disguise. The trick is noticing that the matrix is laid out so that the whole thing is already one big sorted sequence.
Problem. You are given an m x n matrix where each row is sorted left to right, and the first
value of every row is greater than the last value of the previous row. Return true if target is in
the matrix, otherwise false.
Example: matrix = [[1, 4, 7, 11], [15, 18, 21, 23], [30, 34, 37, 41]], target = 34 → true.
The slow way first
The obvious idea: scan every cell and compare it to the target. That is O(m·n) — for a large grid it reads everything. We can do better, because the matrix is far more ordered than a random grid.
The question to ask: if I flatten the rows end to end, what do I get? Reading row 0, then row 1, then row 2 gives 1, 4, 7, 11, 15, 18, 21, 23, 30, 34, 37, 41 — a fully sorted array. And a sorted array is exactly what binary search wants.
The idea: one sorted array, addressed by index
Pretend the grid is a flat array of length rows * cols. Binary-search the index range 0 .. rows*cols - 1. The only new piece is converting a flat index mid back into a real cell: the row is mid // cols and the column is mid % cols.
The key insight: we never actually build a flattened array. We binary-search the index and use integer division and modulo to look up the value on demand.
Walk through it
Step through the animation. The mid pointer jumps to the middle index each round, the lo/hi bounds shrink, and visited cells dim. For target = 34, we probe index 5 (18, too small), 8 (30, too small), 10 (37, too big), then 9 (34) — a match. Four reads out of twelve cells.
Pseudocode
rows, cols = number of rows, number of columns
lo = 0, hi = rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
val = matrix[mid // cols][mid % cols] # map flat index to a cell
if val == target: return true
if val < target: lo = mid + 1 # search the right half
else: hi = mid - 1 # search the left half
return falseThe Python solution
def search_matrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
val = matrix[mid // cols][mid % cols]
if val == target:
return True
if val < target:
lo = mid + 1
else:
hi = mid - 1
return Falseloandhiare flat indices, not row/column pairs — they range over0 .. rows*cols - 1.mid = (lo + hi) // 2is the standard binary-search midpoint.- Line 6 is the heart of the trick:
mid // colsgives the row andmid % colsgives the column, so one flat index reads one real cell. - If
val < targetthe answer is to the right, so we raiselo; otherwise we lowerhi. - The loop ends when
lopasseshi, meaning the value is not present.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (scan all cells) | O(m·n) (moderate) | reads every cell |
| Row scan + per-row search | O(m + log n) (moderate) | find the row, then search it |
| Flattened binary search | O(log (m·n)) (moderate) | one binary search over the whole grid |
O(1) (fast)We treat m·n cells as a single sorted array and binary-search it, so the work is logarithmic in the total number of cells, with no extra space.
When this pattern shows up
Whenever data is sorted — or can be viewed as sorted — think binary search before you think scanning.
A 2D grid with sorted rows that chain together is just a 1D sorted array wearing a costume; the index
mapping row = i // cols, col = i % cols is the same trick used to flatten any grid.
This only works because each row starts higher than the previous row ends. If rows are sorted but do not chain (a different problem), the flat sequence is not globally sorted, and you must use the staircase walk from the top-right corner instead.
Practice
With lo = 0 and hi = 11 and cols = 4, the first mid is 5. Which cell does index 5 map to?
1. Why can we binary-search this matrix as if it were one array?
2. How do we convert a flat index mid into a row and column?
3. What is the time complexity of the flattened binary search?
4. How much extra space does this solution use?