LeetCode:240. 搜索二维矩阵 II,二分查找,详细注释
原题链接:https://leetcode.cn/problems/search-a-2d-matrix-ii/
解题思路:
每一行都是递增的,那就意味着可以对每一行做二分查找
如果找到了
target
就返回true
,如果查找完所有行都没有找到target
,返回false
如何二分查找:
首先声明左边界
let left = 1
,右边界let right = 1000
计算它们的中间值,
const middle = (left + right) >> 1
,或者可以用const middle = Math.floor((left + right) / 2)
如果中间值等于
target
,说明找到了target
如果中间值大于
target
,说明target
的值在left
和middle
之间,因此可以让right = middle - 1
,继续在left
和middle - 1
之间查找target
如果中间值小于
target
,说明target
的值在middle
和right
之间,因此可以让left = middle + 1
,继续在right
和middle + 1
之间查找target
复制代码
复杂度分析
时间复杂度:
O(mlogn)
(m
为行数,n
为列数)。对一行使用二分查找的时间复杂度为O(logn)
,最多需要进行m
次二分查找。空间复杂度:
O(1)
。
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/efee0e9aef1c84e88a9c1a523】。文章转载请联系作者。
评论