Search a 2D Matrix
Write an efficient algorithm that searches for a value target in an m x n integer matrix. The matrix has two properties: (1) integers in each row are sorted left to right, and (2) the first integer of each row is greater than the last integer of the previous row.
- m == matrix.length, n == matrix[i].length
- 1 <= m, n <= 100
- -10^4 <= matrix[i][j], target <= 10^4
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3trueA 2D matrix usually suggests a nested loop search (O(M * N)). However, this specific matrix has two unique properties that change everything.
Property (1) says rows are sorted. Property (2) says the start of a row is larger than the end of the previous one.
Discovery: This is not a 2D matrix; it is a single 1D sorted array that has been "folded" or "coiled" into rows like a long ribbon.
Because it's just a folded 1D array, we can use binary search on the entire grid at once. We treat the grid as if it had a single range from 0 to (Rows * Cols - 1).
When we pick a "middle" index in this virtual 1D array, we just need a little bit of math to find its row and column:
- Row = mid / TotalColumns
- Column = mid % TotalColumns
ROWS = matrix.length
COLS = matrix[0].length
left = 0
right = (ROWS * COLS) - 1
WHILE left <= right:
mid = left + (right - left) / 2
// Map virtual index back to 2D
r = mid / COLS
c = mid % COLS
IF matrix[r][c] == target:
RETURN true
ELSE IF matrix[r][c] < target:
left = mid + 1
ELSE:
right = mid - 1
RETURN falseBy "virtualizing" the 1D search, we achieve the absolute theoretical minimum complexity: O(log(M * N)). We don't have to decide which row to search first; the binary search automatically navigates the whole grid, treating it as a single monotone landscape.
Treat 2D Matrix as 1D Array
Because each row continues from the last, we can perform standard Binary Search on indices 0 to 11.