二维矩阵查找

行间整体有序的矩阵如何查找？

• 矩阵性质: 每行升序, 且每行首元素大于上一行末元素, 整体可看成一维升序数组;
• 做法: 两次二分, 先用每行首元素定位所在行, 再在行内二分;
• 定位行时若 target 大于 matrix[mid][0], 还要与 matrix[mid][n-1] 比较判断是否落在本行;
• 定位完成后需要检查行下标是否越界;

function searchMatrixSorted(matrix: number[][], target: number): boolean {
  const m = matrix.length;
  const n = matrix[0].length;

  let left = 0;
  let right = m;
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (target === matrix[mid][0]) return true;
    else if (target < matrix[mid][0]) right = mid;
    else {
      if (target <= matrix[mid][n - 1]) {
        left = mid;
        break;
      }
      left = mid + 1;
    }
  }
  if (left >= m) return false;
  const row = left;

  left = 0;
  right = n;
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (target === matrix[row][mid]) return true;
    else if (target < matrix[row][mid]) right = mid;
    else left = mid + 1;
  }
  return false;
}

• 时间复杂度: O(log m + log n);
• 空间复杂度: O(1);

行与列都升序的矩阵如何查找？

• 矩阵性质: 每行升序、每列升序, 但不要求行间整体有序;
• 也可以逐行二分, 每行 O(log n), 总计 O(m log n);
• 更优做法: 从右上角出发, 该位置是本行最大、本列最小;
  • 等于 target: 命中;
  • 大于 target: 该列下方只会更大, col--;
  • 小于 target: 该行左侧只会更小, row++;
• 走出边界说明不存在;

function searchMatrixTopRight(matrix: number[][], target: number): boolean {
  let row = 0;
  let col = matrix[0].length - 1;
  while (row < matrix.length && col >= 0) {
    const current = matrix[row][col];
    if (target === current) return true;
    if (target < current) col--;
    else row++;
  }
  return false;
}

• 时间复杂度: O(m + n), 每轮排除一整行或一整列;
• 空间复杂度: O(1);