074. 搜索二维矩阵

题目描述:

难度：Middle

相关话题：数组、二分查找

编写一个高效的算法来判断m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。

• 每行的第一个整数大于前一行的最后一个整数。

示例1:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

示例2:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
输出: false

---

思路：

方法一：O(m+n)，m为行高，n为列宽。

根据矩阵性质，从第一行开始，检查每一行的最后一列，如果存在matrix[i][n-1]>=target，说明target只有可能在当前行，再遍历检查当前行。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：前端中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
  if(matrix.length===0)return false
  let m=matrix.length,n=matrix[0].length
  let searchRow=null
  for(let i=0;i<m;i++){
    if(matrix[i][n-1]>=target){
      searchRow=i
      break
    }
  }
  if(searchRow==null)return false
  for(let i=0;i<n;i++){
    if(matrix[searchRow][i]===target)return true
  }
  return false
};

方法二：O(log(m*n))

思路是将二维矩阵转化为一维数组(当然不需要真的转换，只需索引在一维和二维互相转换)，通过索引进行二分搜索。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
  if(matrix.length===0)return false
  let m=matrix.length,n=matrix[0].length
  let lo=0,hi=m*n-1
  while(lo<=hi){
    let mid=Math.floor((lo+hi)/2)
    let [x,y]=to2(mid)
    let midV=matrix[x][y]
    if(midV===target)return true
    else if(midV<target)lo=mid+1
    else hi=mid-1
  }
  return false

  function to2(x){
    return [Math.floor(x/n),x%n]
  }
  function to1([x,y]){
    return x*m+y
  }
};