当前位置:   article > 正文

二分查找的最多比较次数_二分查找最多查找的次数

二分查找最多查找的次数

答案

对于二分搜索次数最多的问题,计算公式为a < log_2(n) < b,其中a , b , n 均为整数

顺序表有n个关键字时候,查找失败,至少需要比较a次关键字

查找成功,至少需要b次

举例

已有从小到大排序的10000个数据,用二分查找法检索最多查14次即可得出结论。

当顺序表有n个关键字时:查找失败时,至少比较a次关键字;查找成功时,最多比较关键字次数是b。因为2^13-1=8191,2^14-1=16383,所以13<log2(10000)<14。

疑惑

其实一直都有一个疑惑,二分查找最多几次?对于n个元素,第一次查找会变成n/2 ,第二次查找就会变成n/4,...,第k次查找元素个数就会变成n/(2^k),最坏的情况就是剩下1个元素,那就是他了,于是解方程 \frac{n}{2^k}=1,解得k=log_2(n),log2(n)一般不会是整数,到底应该向下取整?还是应该向上取整?

解答疑惑:log2(n)在不是整数的时候向下取整+1 就是向上取整了

在这篇文章里面还有另外一种算法

我们对上述发现的规律进行归纳证明:

假设对于区间长度为[2^{(k-1)} ,2^k-1]的区间,最多比较k次
则对于区间长度为[2^k , 2^{(k+1)}-1][2^k, 2^{(k+1)}-1]的区间,假设区间长度为x
如果区间长度为奇数,那么第一次比较以后左右两个区间的长度在2^(k-1) ~ 2^k-1之间,加上第一次比较,最多比较k+1次
如果区间长度为偶数,那么第一次比较以后较大的区间为长度为偶数的区间,此区间的长度仍然在2^(k-1) ~ 2^k-1之间,加上第一次比较,最多比较k+1次

综上对于区间长度为2^(k-1) ~ 2^k-1的区间,最多比较k次(k>=1),即对于区间长度y,最多比较logy+1次

对于标准的二分查找,我们每次从区间[left,right)中取一个值,和中间值mid=(left+right)>>1进行比较,然后将数组分为[left,mid) [mid+1,right),即每次将区间长度x变为(x-1)>>1。最大比较次数显然是我们想要查找的数并不在数组中的时候,这样的话我们需要将区间长度变为0才能结束比较。这样直接分析有些困难,因此我们不妨换一个思路。

如果区间长度为1,显然最多比较1次
区间长度为2,最多比较2次([0,2) -> [0,1) -> [0,0)),log_2(2)=1,可以理解为最多比较log2(2)+1次,也可以理解为,0<log2(2)<2 查找成功需要2次
区间长度为3,最多比较2次([0,3) -> [0,1) [2,3)),可以理解为,log2(3)+1=2次(向下取整),也可以理解为,1<log2(3)<2,查找成功需要2次
区间长度为4,最多比较3次

下标为0,1,2,3

[0,4)开始

->mid=(0+3)/2向下取整=1,[0,1) [2,4)

->mid=(2+3)/2向下取整=2,

->如果不是2,那区间范围里面只剩下一个元素3,在查找一次

可以理解为,log2(4)+1=3次,也可以理解为 1<log2(4)<3,查找成功需要3次。

区间长度为10,3<log2(10)<4,查找成功需要4次比较,log2(10)+1=4次

下标为0,1,2,3,4,5,6,7,8,9

[0,10)开始

->mid=(0+9)/2向下取整=4,[0,4) [5,10)

->mid=(5+9)/2向下取整=7,[5,7) [8,10)

->mid=(5+7)/2向下取整=6,[5] [7]

->再查找一次,才会得到最后的答案

因此我们不难得到规律:
如果最多比较x次,则区间长度为2^(x-1) ~ 2^x-1
对于区间长度y,最多比较logy+1次

那么当n=1000的时候,9 <log2(1000)<10,最大的查找次数是10。 也可以这么理解log2(1000)+1=10,他是向下取整然后再+1

代码细节

每次二分时 mid=(left + right)/ 2 都是向下取整的;
每次比较后,如果没找到,就放弃当前比较的值,right = mid - 1 / left = mid + 1。

二分查找有两种写法,一种是左闭右闭区间,一种是左闭右开区间

 第一种写法就是,左闭右闭区间

if (nums[middle] > target)              right = middle-1;

else if (nums[middle] < target)      left = middle + 1;

else { // nums[middle] == target   return middle; 

对于左闭右闭区间,循环的入口条件是 left <= right 

  1. def binarySearch(list, target):
  2. lo = 0
  3. hi = len(list) - 1
  4. while lo <= hi: #细节1:循环入口条件
  5. mid = (lo + hi) // 2 #细节2:向下取整
  6. if list[mid] == target:
  7. return mid
  8. #细节3:选取区间,反正就一个主要原则,不能包含,mid这个已经选出来比较过的值
  9. elif list[mid] < target:
  10. lo = mid + 1
  11. else:
  12. hi = mid - 1
  13. return None

 注意这是个左闭右闭的闭区间,单纯从数学角度出发,这个区间最短的长度就是1,也就是left=right的时候。如果left>right了,那[left,right]就是空集,这个集合肯定不包含目标值,也就没有继续搜索的必要了,所以循环退出。

 第二种写法就是,左闭右开区间

如果说定义 target 是在一个在左闭右开的区间里,也就是[left, right) ,那么二分法的边界处理方式则截然不同。

有如下两点:

  • while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的
  • if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]

 代码复制来源于代码随想录,就是大概看个意思

if (nums[middle] > target)              right = middle

else if (nums[middle] < target)      left = middle + 1;

else { // nums[middle] == target   return middle; 

  1. // 版本二
  2. class Solution {
  3. public:
  4. int search(vector<int>& nums, int target) {
  5. int left = 0;
  6. int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right)
  7. while (left < right) { // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
  8. int middle = left + ((right - left) >> 1);
  9. if (nums[middle] > target) {
  10. right = middle; // target 在左区间,在[left, middle)中
  11. } else if (nums[middle] < target) {
  12. left = middle + 1; // target 在右区间,在[middle + 1, right)中
  13. } else { // nums[middle] == target
  14. return middle; // 数组中找到目标值,直接返回下标
  15. }
  16. }
  17. // 未找到目标值
  18. return -1;
  19. }
  20. };

二分法是非常重要的基础算法,为什么很多同学对于二分法都是一看就会,一写就废

其实主要就是对区间的定义没有理解清楚,在循环中没有始终坚持根据查找区间的定义来做边界处理。

Leecode相关题目:

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

闽ICP备14008679号