Search a 2D Matrix

The problem. You're given an m × n integer matrix where each row is sorted, and each row starts with a value bigger than the last value of the row before. Given a target, return true if it's in the matrix. Your solution must run in O(log(m · n)) time.

Example

matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3   ->  true
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 13  ->  false

The pattern: searching a 2D matrix

Sorted matrices come in two kinds, and each has its own trick. When rows continue one another, as here, the whole matrix is secretly one sorted list: binary search it with index arithmetic. When rows and columns are only sorted separately (next lesson), start in a corner where one comparison rules out a whole row or column.

1. Check every cell

1function searchMatrix(matrix, target) {2  for (const row of matrix) {3    for (const value of row) if (value === target) return true;4  }5  return false;6}

Time O(m · n), space O(1).

2. Find the row, then search it

First binary search the rows for the last row whose first value is at most the target — the only row that could hold it. Then binary search inside that row.

1function searchMatrix(matrix, target) {2  let low = 0, high = matrix.length - 1;3  while (low < high) {                           // the last row starting at or below target4    const mid = low + Math.ceil((high - low) / 2);   // round up: low = mid must make progress5    if (matrix[mid][0] <= target) low = mid;6    else high = mid - 1;7  }8  const row = matrix[low];9  let l = 0, h = row.length - 1;10  while (l <= h) {                               // plain binary search in that row11    const mid = l + Math.floor((h - l) / 2);12    if (row[mid] === target) return true;13    if (row[mid] < target) l = mid + 1;14    else h = mid - 1;15  }16  return false;17}

Time O(log m + log n) = O(log(m · n)), space O(1). Note the last-yes search for the row: mid rounds up so that low = mid always moves.

3. One binary search over the whole matrix

1function searchMatrix(matrix, target) {2  const rows = matrix.length, cols = matrix[0].length;3  let low = 0, high = rows * cols - 1;4  while (low <= high) {5    const mid = Math.floor((low + high) / 2);6    const r = Math.floor(mid / cols), c = mid % cols;7    if (matrix[r][c] === target) return true;8    if (matrix[r][c] < target) low = mid + 1;9    else high = mid - 1;10  }11  return false;12}

Time O(log(m · n)), space O(1). The matrix is never copied: mid / cols and mid % cols turn a position in the imaginary flat list into a real row and column.

Comparing the approaches

Edge cases to test

Variations