写点什么

LeetCode:240. 搜索二维矩阵 II,二分查找,详细注释

作者:Lee Chen
  • 2023-02-20
    福建
  • 本文字数:892 字

    阅读完需:约 3 分钟

LeetCode:240. 搜索二维矩阵 II,二分查找,详细注释

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


解题思路:

  1. 每一行都是递增的,那就意味着可以对每一行做二分查找

  2. 如果找到了target就返回true,如果查找完所有行都没有找到target,返回false

  3. 如何二分查找:

  4. 首先声明左边界let left = 1,右边界let right = 1000

  5. 计算它们的中间值,const middle = (left + right) >> 1,或者可以用const middle = Math.floor((left + right) / 2)

  6. 如果中间值等于target,说明找到了target

  7. 如果中间值大于target,说明target的值在leftmiddle之间,因此可以让right = middle - 1,继续在leftmiddle - 1之间查找target

  8. 如果中间值小于target,说明target的值在middleright之间,因此可以让left = middle + 1,继续在rightmiddle + 1之间查找target


/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */var searchMatrix = function (matrix, target) {  // 枚举每一行  for (const row of matrix) {    // 在每一行中,使用二分查找搜索是否有数字等于target    if (binarySearch(row, target)) {      return true    }  }
return false}
// 二分查找const binarySearch = (row, target) => { let left = 0 // 左边界 let right = row.length - 1 // 右边界
// 不断搜索直到两个指针相遇 while (left <= right) { // 每次取中间索引 const middle = (left + right) >> 1 // 查找到中间位置的值 const middleItem = row[middle]
// 如果查找到target,返回true if (middleItem === target) { return true } // 如果中间值大于target,说明target在左半边 // 将右边界移动到middle - 1 else if (middleItem > target) { right = middle - 1 } // 如果中间值小于target,说明target在右半边 // 将左边界移动到middle + 1 else { left = middle + 1 } }
return false}
复制代码


复杂度分析

  • 时间复杂度:O(mlog⁡n)m为行数,n为列数)。对一行使用二分查找的时间复杂度为O(log⁡n),最多需要进行m次二分查找。

  • 空间复杂度:O(1)

发布于: 刚刚阅读数: 3
用户头像

Lee Chen

关注

还未添加个人签名 2018-08-29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode:240. 搜索二维矩阵 II,二分查找,详细注释_JavaScript_Lee Chen_InfoQ写作社区