[!info] related notes 算法面试题型 MOC 二分查找

搜索二维矩阵

题目

74. 搜索二维矩阵 - 力扣（LeetCode）

思路

题目保证非空规则矩阵，每行非递减，且下一行首元素大于上一行尾元素。因此按行展平后整体有序。只有“每行每列分别有序”不够，例如 [[1, 4], [2, 5]] 不能直接展平二分；这种较弱前提见 有序矩阵第 K 小。

所以整体等价于一个长度为 m*n 的一维递增数组：

• idx -> (row, col)：row = Math.floor(idx / n)，col = idx % n

这里只映射下标，不创建展平数组。时间 O(log(mn))，额外空间 O(1)；题外若允许空矩阵，应在访问 matrix[0] 前处理。

代码（JavaScript）

var searchMatrix = function(matrix, target) {
  const m = matrix.length;
  const n = matrix[0].length;
  let l = 0, r = m * n - 1;
  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    const i = Math.floor(mid / n);
    const j = mid % n;
    const v = matrix[i][j];
    if (v === target) return true;
    if (v < target) l = mid + 1;
    else r = mid - 1;
  }
  return false;
};