74. Search a 2D Matrix

Each row of an m×n matrix is sorted, and each row's first value is greater than the previous row's last. Return true if target is in the matrix, in O(log(m·n)) time.

Rows are sorted and each row starts after the previous ends, so the matrix is one sorted array of m·n values. Index k maps to (⌊k/n⌋, k mod n).

1function searchMatrix(matrix: number[][], target: number): boolean {
2  const m = matrix.length, n = matrix[0].length;
3  let lo = 0, hi = m * n - 1;
4  while (lo <= hi) {
5    const mid = (lo + hi) >> 1;
6    const v = matrix[Math.floor(mid / n)][mid % n];
7    if (v === target) return true;
8    if (v < target) lo = mid + 1;
9    else hi = mid - 1;
10  }
11  return false;
12}

target = 16lo = 0hi = 11

matrix

1	3	5	7
10	11	16	20
23	30	34	60

Search flat indices 0..11.

1 / 0

Space: play/pause · ←/→: step