240. 搜索二维矩阵 II（JS实现）

最新推荐文章于 2025-05-22 23:49:05 发布

PAT-python-zjw

最新推荐文章于 2025-05-22 23:49:05 发布

阅读量523

点赞数

分类专栏：剑指offer

本文为博主原创文章，转载请务必附上文章网址，谢谢。

本文链接：https://blog.csdn.net/zjw_python/article/details/108028892

版权

剑指offer 专栏收录该内容

153 篇文章

订阅专栏

本文介绍了一种在有序二维矩阵中高效查找目标值的算法。通过使用双指针法，从矩阵的左下角开始，根据目标值与当前值的比较结果，决定向上或向右移动，直至找到目标值或确定目标值不存在于矩阵中。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1 题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。

链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii

2 思路

**我是用二分法做的，并不是最优解，题解中有一种双指针法很巧妙
首先，我们初始化一个指向矩阵左下角的 (row，col)(row，col) 指针。然后，直到找到目标并返回 true（或者指针指向矩阵维度之外的 (row，col)(row，col) 为止，我们执行以下操作：如果当前指向的值大于目标值，则可以 “向上” 移动一行。否则，如果当前指向的值小于目标值，则可以移动一列。不难理解为什么这样做永远不会删减正确的答案；因为行是从左到右排序的，所以我们知道当前值右侧的每个值都较大。因此，如果当前值已经大于目标值，我们知道它右边的每个值会比较大。也可以对列进行非常类似的论证，因此这种搜索方式将始终在矩阵中找到目标（如果存在）
**

3代码

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
  let rows = matrix.length;
  if (rows === 0) return false;
  let cols = matrix[0].length;
  if (cols === 0) return false;

  if (target < matrix[0][0] || target > matrix[rows-1][cols-1]) return false;

  let low = 0;
  let high = rows - 1;

  while(low < high) {
    let mid = Math.floor((low + high) / 2);

    if (matrix[mid][0] > target) {
      high = mid - 1;
    } else if (matrix[mid][cols-1] < target) {
      low = mid + 1;
    } else {
      break;
    }
  }

  let currentRow = low;

  while(currentRow <= high) {
    let low1 = 0;
    let high1 = cols - 1;

    while(low1 <= high1) {
      let mid = Math.floor((low1 + high1) / 2);

      if (matrix[currentRow][mid] > target) {
        high1 = mid - 1;
      } else if (matrix[currentRow][mid] < target) {
        low1 = mid + 1;
      } else {
        return true;
      }
    }

    currentRow++;
  }

  return false;
};