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

答案

对于二分搜索次数最多的问题，计算公式为，其中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个元素，那就是他了，于是解方程 ，解得，log2(n)一般不会是整数，到底应该向下取整？还是应该向上取整？

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

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

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

假设对于区间长度为的区间，最多比较k次
则对于区间长度为的区间，假设区间长度为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)）,，可以理解为最多比较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 

def binarySearch(list, target):
  lo = 0
  hi = len(list) - 1
  while lo <= hi: #细节1：循环入口条件
    mid = (lo + hi) // 2 #细节2：向下取整
    if list[mid] == target:
      return mid
    #细节3:选取区间，反正就一个主要原则，不能包含，mid这个已经选出来比较过的值
    elif list[mid] < target:
      lo = mid + 1
    else:
      hi = mid - 1
  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; 

// 版本二
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

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

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

Leecode相关题目：

• 35.搜索插入位置(opens new window)
• 34.在排序数组中查找元素的第一个和最后一个位置(opens new window)
• 69.x 的平方根
• 367.有效的完全平方数