搜索二维矩阵

LeetCode 74：把二维矩阵视为一维有序数组做二分。

#resource / algorithm #type / howto #status / evergreen #source / leetcode #algo / binary-search #ds / array

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

搜索二维矩阵

题目

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

思路

题目保证：每行递增，且下一行的首元素大于上一行的尾元素。

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

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

代码（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;
};