数组01-二分查找

Posted on

二分作为大一就没有搞懂的硬骨头,模糊的主要原因是区分不了二分查找和二分答案

而且网上的二分答案模板实在是太多太多了 自己刷的题目数量也没跟上,导致模板总是忘

借着这个博客,彻底搞懂二分!!😡

这个博客只讨论二分查找 不要搞混

首先 ,看了代码随想录的视频,感觉它的角度很新奇,二分的模板是根据你对数组边界的定义来决定的

它把二分的模板分成了两种:

  • 左闭右闭 [left,right]
  • 左闭右开 [left,right)

模板一 左闭右闭

起始两种的区别就在于 更新边界时是否需要考虑mid+1或者mid-1处理 因为边界定义不同,边界取值也就不一样

左闭右闭的情况下, 右边界的值考虑进去,那么:

  • while(left right) 此处就应该是<= ,因为右边界是闭,我们是要允许left == right的情况 比如[1,1]
  • if mid > target 那么此时 r=mid-1 , 因为mid作为右边界是被考虑的,可是mid我们已经判定过了,所以在下一次的搜索中,需要把mid扔出去.

因此 模板一的完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def search(self, nums, target):
      	left=0
        right=len(nums)-1
        
        while left<=right:
            mid=left+(right-left)//2  #中间值的安全取法 防止溢出
            
            if nums[mid] ==target:
                return mid
            elif nums[mid]> target:
                right=mid-1
            else:
                left=mid+1
        return -1

模板二 : 左闭右开

左闭右开的情况就和模板一有一些不同

  • while left right 中见的内容就是 < 因为右边界不取 不允许出现left == right 比如 [1,1)
  • if mid > target 那么left =mid 就不需要mid-1 因为右边界反正不取 不要多此一举
  • right=len(nums) 这里右边界取不到 所以right初始化不能为len(nums)-1!!

那么代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def search(self, nums, target):
      	left=0
        right=len(nums)
        
        while left<right:
            mid=left+(right-left)//2  #中间值的安全取法 防止溢出
            
            if nums[mid] ==target:
                return mid
            elif nums[mid]> target:
                right=mid
            else:
                left=mid+1
        return -1