Search a 2D Matrix

MediumBinary SearchArrayBinary SearchMatrix

Problem

You are given a matrix where each row is sorted left to right, and the first value of every row is greater than the last value of the row above it. Given a target integer, determine whether it exists anywhere in the matrix.

Example. For [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] and a target of 16, the answer is true.

Key idea

Binary searching each row separately works, but repeats a logarithmic search once per row. The matrix actually behaves like one long sorted array once row length is accounted for: read row by row, and the values never decrease. A single binary search can then work directly over the matrix without ever building a flattened copy.

Treat the matrix as n * m virtual positions numbered 0 through n * m - 1. Convert a position to a real cell by dividing by the row width for the row, and taking the remainder for the column. Run ordinary binary search over that virtual range, narrowing the low or high bound exactly as in a flat sorted array. Because translating an index into a cell is O(1), the search behaves identically to searching one sorted list of the same length.

Solution

function searchMatrix(matrix: number[][], target: number): boolean {
  const rowCount = matrix.length;
  if (rowCount === 0) {
    return false;
  }
  const colCount = matrix[0].length;

  let low = 0;
  // treat the matrix as one flat sorted array of rowCount * colCount cells
  let high = rowCount * colCount - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    // map the flat index back to its real row and column
    const row = Math.floor(mid / colCount);
    const col = mid % colCount;
    const value = matrix[row][col];

    if (value === target) {
      return true;
    } else if (value < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return false;
}

Complexity

  • Time: O(log(n * m)). One binary search over all cells treated as a single sorted sequence.
  • Space: O(1). Only the boundary indices and their derived row and column are kept.

Watch out for

  • The division and remainder must use the actual row width, not the matrix's total size, or the mapping breaks.
  • This shortcut relies on rows continuing where the previous one left off; a matrix sorted only within rows and columns needs a different approach.

Pattern

This is binary search over an implicit index mapping: instead of a literal array, you search a coordinate space and translate each candidate back to a real position. The same trick of collapsing a two-dimensional structure into one sorted dimension reappears whenever extra structure lets you avoid a nested search.

Related questions