当前位置:   article > 正文

二分查找详解_def binarysearch

def binarysearch

1 二分查找的基本框架

  1. def binarySearch(nums,target):
  2. left=0
  3. right=...
  4. while(...):
  5. mid=left+(right-left)//2
  6. #防止溢出
  7. if(nums[mid]==target):
  8. ...
  9. elif(nums[mid]<target):
  10. ...
  11. elif(nums[mid]>target):
  12. ...
  13. return ...
'
运行

几个tips:

1,二分查找尽量不要出现else,而是把所有情况有else if写清楚,这样可以清楚地显示所有的细节。

2,计算mid的时候,为了防止溢出,建议写成: mid = left + (right - left) / 2

2 目标:寻找一个数

2.1 代码框架

  1. def binarySearch(nums,target):
  2. left=0
  3. right=len(nums)-1
  4. while(left<=right):
  5. mid=left+(right-left)//2
  6. #防止溢出
  7. if(nums[mid]==target):
  8. return mid
  9. elif(nums[mid]<target):
  10. left=mid+1
  11. elif(nums[mid]>target):
  12. right=mid-1
  13. return -1
'
运行

2.2 为什么 while 循环的条件中是 <=,而不是 < ?

因为初始化 right 的赋值是 nums.length - 1,即最后一个元素的索引,而不是 nums.length。

这二者可能出现在不同功能的二分查找中,区别是:前者相当于两端都闭区间 [left, right],后者相当于左闭右开区间 [left, right),因为索引大小为 nums.length 是越界的。

我们在上面这个代码中使用的是 [left, right] 两端都闭的区间。这个区间就是每次进行搜索的区间

什么时候应该停止搜索呢?

1)找到了目标值的时候(即nums[mid]==target)

2)没有找到目标值的时候

如果没找到,就需要 while 循环终止,然后返回 -1。那 while 循环什么时候应该终止?搜索区间为空的时候应该终止,意味着你没得找了,就等于没找到。

while(left <= right)的终止条件是 left == right + 1,写成区间的形式就是 [right + 1, right],或者带个具体的数字进去 [3, 2],可见这时候搜索区间为空,因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的,直接返回 -1 即可。

while(left < right)的终止条件是 left == right,写成区间的形式就是 [right, right],或者带个具体的数字进去 [2, 2],这时候搜索区间非空,还有一个数 2,但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了,索引 2 没有被搜索,如果这时候直接返回 -1 就可能出现错误。(因为没有考虑left==right时候这个点的值是否满足条件)

2.3 为什么 left = mid + 1,right = mid - 1?这些加加减减怎么判断?

这也是二分查找的一个难点,不过只要你能理解前面的内容,就能够很容易判断。

2.2节明确了搜索区间这个概念,而且本算法的搜索区间是两端都闭的,即 [left, right]。

那么当我们发现索引 mid 不是要找的 target 时,如何确定下一步的搜索区间呢?

当然是去搜索 [left, mid - 1] 或者 [mid + 1, right] 。因为 mid 已经搜索过,应该从搜索区间中去除。

2.4 此算法有什么缺陷?

比如说给你有序数组 nums = [1,2,2,2,3],target = 2,此算法返回的索引是 2,没错。

但是如果我想得到 target 的左侧边界,即索引 1,或者我想得到 target 的右侧边界,即索引 3,这样的话此算法是无法处理的。

这样的需求很常见。你也许会说,找到一个 target 索引,然后向左或向右线性搜索不行吗?可以,但是不好,因为这样难以保证二分查找对数级的时间复杂度了。

3 二分搜索变体:寻找左侧边界的二分搜索

3.1 代码框架

  1. def binarySearch(nums,target):
  2. left=0
  3. right=len(nums)
  4. while(left<right):
  5. mid=left+(right-left)//2
  6. #防止溢出
  7. if(nums[mid]==target):
  8. right= mid
  9. elif(nums[mid]<target):
  10. left=mid+1
  11. elif(nums[mid]>target):
  12. right=mid
  13. return left
'
运行

3.2 为什么 while(left < right) 而不是 <= ?

用相同的方法分析,因为我们这里初始化 right = nums.length 而不是 nums.length - 1 。因此每次循环的「搜索区间」是 [left, right) 左闭右开。

while(left < right) 终止的条件是 left == right,此时搜索区间 [left, left) 恰巧为空,所以可以正确终止。

3.3 为什么没有返回 -1 的操作?如果 nums 中不存在 target 这个值,怎么办?

我们一步一步来,先理解一下这个左侧边界有什么特殊含义:

对于这个数组,算法会返回 1。这个 1 的含义可以这样解读:nums 中小于 2 的元素有 1 个。(或者:第一次出现大于等于2的时候的坐标是1)

比如对于有序数组 nums = [2,3,5,7], target = 1,算法会返回 0,含义是:nums 中小于 1 的元素有 0 个。(第一次出现大于等于0的时候的坐标是0)

如果 target = 8,算法会返回 4,含义是:nums 中小于 8 的元素有 4 个。(第一次出现大于等于8的时候的坐标是4)

综上可以看出,函数的返回值(即 left 变量的值)取值区间是闭区间 [0, nums.length](所以right的初始化时len(nums))

3.4 为什么 left = mid + 1,right = mid ?

因为我们的搜索区间是 [left, right) 左闭右开,所以当 nums[mid] 被检测之后,下一步的搜索区间应该去掉 mid 分割成两个区间,即 [left, mid) 或 [mid + 1, right)。

3.5 为什么该算法能够搜索左侧边界?

关键在于对于 nums[mid] == target 这种情况的处理

  1. if(nums[mid]==target):
  2. right= mid

可见,找到 target 时不要立即返回,而是缩小「搜索区间」的上界 right,在区间 [left, mid) 中继续搜索,即不断向左收缩,达到锁定左侧边界的目的。

 

3.6 为什么返回 left 而不是 right?

返回left和right都是一样的,因为 while 终止的条件是 left == right。

二分搜索变体:寻找右侧边界的二分搜索

寻找右侧边界和寻找左侧边界的代码差不多,只有两处不同(在4.1中已标注)

4.1 代码框架

  1. def binarySearch(nums,target):
  2. left=0
  3. right=len(nums)
  4. while(left<right):
  5. mid=left+(right-left)//2
  6. #防止溢出
  7. if(nums[mid]==target):
  8. left= mid+1
  9. #不同之处1
  10. elif(nums[mid]<target):
  11. left=mid+1
  12. elif(nums[mid]>target):
  13. right=mid
  14. return left-1
  15. #不同之处2
'
运行

4.2 为什么这个算法能够找到右侧边界?

还是=target的时候的操作:

  1. if(nums[mid]==target):
  2. left= mid+1
  3. #不同之处1

当 nums[mid] == target 时,不要立即返回,而是增大「搜索区间」的下界 left,使得区间不断向右收缩,达到锁定右侧边界的目的。

4.3 为什么最后返回 left - 1 而不像左侧边界的函数,返回 left?或者对偶的返回right?

首先,while 循环的终止条件是 left == right,所以 left 和 right 是一样的。所以如果非要体现右侧的特点,返回 right - 1 就好了。

至于为什么要减一,这是搜索右侧边界的一个特殊点,关键在这个条件判断:

  1. if(nums[mid]==target):
  2. left= mid+1
  3. #不同之处1

此时mid=left-1

因为我们对 left 的更新必须是 left = mid + 1,就是说 while 循环结束时,nums[left] 一定不等于 target 了,而 nums[left - 1]可能是target。

返回的值的意思,小于等于target的元素有几个;或者第一次大于target的元素的坐标。

4.4 为什么 left 的更新必须是 left = mid + 1,

和左侧边界搜索一样,就不再赘述

5 二分查找总结

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/906018
推荐阅读
相关标签
  

闽ICP备14008679号