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

矫情吗；* 2022-11-27 15:35 120阅读 0赞

## 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;
    };