240. 搜索二维矩阵 II(JS实现)

240. 搜索二维矩阵 II(JS实现)
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;
};