手帐 Blog

主题

复盘 · LC 74 搜索二维矩阵 ​

题目 ​

题意 ​

m × n 矩阵满足：

  • 每行从左到右递增；
  • 每行第一个数大于上一行最后一个数。

等价于把矩阵按行拼成一条升序序列。给定 target，判断是否存在。

边界：单行 / 单列 / [[1]]；target 小于矩阵最小或大于最大。

涉及算法 ​

标签一句话
二分查找先定行再定列，或把二维压成一维做一次二分
矩阵有序性质行首递增 → 可用 lower_bound 找行

教程对照：14 · 二分查找标准模板；和 240. 搜索二维矩阵 II 对比——240 没有「行首大于上行末」这条，不能直接当一维数组。

评价我的解法 ​

今天写了两版，进步很明显。

第一版 · 线性找行 + 行内二分（index.js） ​

我的代码（摘自 74-搜索二维矩阵/index.js）：

javascript
var searchMatrix = function (matrix, target) {
  function search(arr, targetNum) {
    let left = 0,
      right = arr.length - 1;
    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (arr[mid] === targetNum) {
        return mid;
      } else if (arr[mid] > targetNum) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return false;
  }
  let suitArr = null;
  for (let i = 0; i < matrix.length; i++) {
    if (matrix[i][0] > target) {
      break;
    }
    suitArr = matrix[i];
  }
  if (!suitArr) {
    return false;
  }
  return search(suitArr, target) !== false;
};
  • 逻辑正确：利用行首递增，取「最后一个 matrix[i][0] <= target 的行」再二分——这是本题合法性质。
  • 复杂度：O(m + log n)，行很多时不如两次二分或一次一维二分。
  • 小瑕疵：search 找到返回下标、找不到返回 false，用 !== false 判断能过，但类型混用（number | false）不如直接返回 boolean。

第二版 · 行二分 + 列二分（index2.js） ​

我的代码（摘自 74-搜索二维矩阵/index2.js）：

javascript
var searchMatrix = function (matrix, target) {
  function searchCol(arr, targetNum) {
    let left = 0,
      right = arr.length - 1;
    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (arr[mid] === targetNum) {
        return mid;
      } else if (arr[mid] > targetNum) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return false;
  }
  function searchRow(arr, targetNum) {
    let left = 0,
      right = arr.length - 1;
    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (arr[mid][0] === targetNum) {
        return mid;
      } else if (arr[mid][0] > targetNum) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
  const row = searchRow(matrix, target);
  if (row < 0 || row > matrix.length) {
    return false;
  }
  if (row < matrix.length && matrix[row][0] === target) {
    return true;
  } else if (row === 0) {
    return false;
  }
  const isFindCol = searchCol(matrix[row - 1], target);
  return isFindCol !== false;
};
  • 已意识到「行也可以二分」，提交到 100% 时间，方向对。
  • searchRow 结束后返回 left，本质是对行首做 lower_bound，再回退到 row - 1 搜——能过，但边界分支（row === 0、命中行首）偏多，口述成本高。
  • 更干净的说法：二分找「最后一个行首 ≤ target 的行」，或直接一维下标二分。

小结：从 O(m) 找行升到行二分，二分肌肉在涨；下一步把「两次二分的边界」收成一种固定说法，或直接默写一维版。

最佳题解 ​

把矩阵当成长度为 m * n 的有序数组做一次二分：

javascript
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  const m = matrix.length;
  const n = matrix[0].length;
  let left = 0;
  let right = m * n - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const val = matrix[Math.floor(mid / n)][mid % n];
    if (val === target) return true;
    if (val < target) left = mid + 1;
    else right = mid - 1;
  }
  return false;
};
  • 时间 O(log(mn))，空间 O(1)。
  • 为何更优：一次模板、无行边界特判；映射 mid → (mid/n, mid%n) 是面试高频一句。

若坚持两次二分：对行首做「最后一个 ≤ target」，再对该行标准二分，语义比「lower_bound 再 -1」更好讲。

关联题目 ​

题为何相关
240. 搜索二维矩阵 II行/列递增但非全局一维；从右上角收缩
35. 搜索插入位置同一套 left/right/mid
33. 搜索旋转排序数组有序被拧了一下，仍是二分变体

一句话带走 ​

74 优先讲：整表当一维有序数组，mid/n 与 mid%n 映射再二分。