Search a 2D Matrix
Treat it as one sorted array
Each row's smallest value exceeds the previous row's largest value, so reading the matrix row by row, left to right, produces one fully sorted sequence. That means there's no need for a 2D search at all — plain binary search over the flattened array finds the target in O(log(rows*cols)).
Details
Animated on: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 (shown flattened row-major into a 12-cell sorted array).
Problem:Search a 2D MatrixMedium
Treat it as one sorted array
step 1 / 9
Each row's values exceed the previous row's, so the flattened matrix is fully sorted — binary search works directly. target=3.
- low=0· arr[0] = 1
- high=11· arr[11] = 60
1FUNCTION searchMatrix(matrix, target):2 flat = read the matrix row by row into one list (already sorted, since each row's values exceed the previous row's)3 low = 0, high = the length of flat - 14 WHILE low <= high:5 mid = (low + high) / 2, rounded down6 IF flat[mid] equals target: RETURN true7 ELSE IF flat[mid] > target: high = mid - 18 ELSE: low = mid + 19 RETURN false
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- Each row's values exceed the previous row's, so the flattened matrix is fully sorted — binary search works directly. target=3.
- mid = (0+11)/2 = 5 → value 11. 11 > 3, so search the left half.
- Narrow the search to low=0, high=4.
- mid = (0+4)/2 = 2 → value 5. 5 > 3, search the left half again.
- Narrow the search to low=0, high=1.
- mid = (0+1)/2 = 0 → value 1. 1 < 3, so search the right half.
- Narrow the search to low=1, high=1.
- mid = (1+1)/2 = 1 → value 3. 3 === 3 — found!
- Target 3 found at flattened index 1 (row0, col1 in the original matrix). Answer: true.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.