22 Mar 2025•TypeScript•Medium

Search a 2D Matrix

binary search on a sorted 2d matrix by treating it as a flattened sorted array.

since the matrix is sorted row-wise and each row starts after the previous ends, we can treat it as a single sorted array. i use binary search with index conversion: mid index maps to row = floor(mid / cols) and col = mid % cols.

this gives us O(log(mn)) time complexity, same as binary search on a flat array, but we work directly with the 2d structure.

key insight

the matrix is essentially a sorted array stored in row-major order. by converting linear indices to 2d coordinates, we can apply standard binary search.

complexity

O(log(mn)) time where m and n are dimensions, O(1) space. standard binary search efficiency.

Solution files

TypeScript•search-a-2d-matrix/solution.ts

function searchMatrix(matrix: number[][], target: number): boolean {
  if (matrix.length === class="syntax-number">0 || matrix[class="syntax-number">0].length === class="syntax-number">0) {
    return false;
  }

  const rows = matrix.length;
  const cols = matrix[class="syntax-number">0].length;
  let lo = class="syntax-number">0;
  let hi = rows * cols - class="syntax-number">1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / class="syntax-number">2);
    const r = Math.floor(mid / cols);
    const c = mid % cols;
    const value = matrix[r][c];

    if (value === target) {
      return true;
    }

    if (value < target) {
      lo = mid + class="syntax-number">1;
    } else {
      hi = mid - class="syntax-number">1;
    }
  }

  return false;
}

export { searchMatrix };