二进制搜索（1 + log（n））而不是log（n）中最大键的比较？

Question

我正在对BS进行更为通用的解释。它的前提是二进制搜索中最大键比较数为（1 + log（n））。我试图就这种可能性如何形成直觉。我知道BS的毁灭时间是（log（n））。我还推测，当我们搜索数组中不存在的元素时，最坏的时间/最大键查找将会发生。但是每次我经过假设的阵列进行BS运算时，我最终都会以（log（n））进行比较/步进。这是用来构成该介词的代码。

public static int binarySearch(int[] a, int key){
     int lo = 0, hi = a.length-1;
     while (lo <= hi){
         int mid = lo + (hi - lo) / 2;

         if (key < a[mid]) 
            hi = mid - 1;
         else if (key > a[mid]) 
            lo = mid + 1;
         else 
            return mid;
     }
     return -1;
 }

[我的推测可能是错误的，或者我遗漏了一些要点。如果您能解释最大可能的键比较是（1 + log（n）），将非常感谢。

Answer 1

不要忘记，即使只有1个元素，也仍然要猜测，因为目标很可能不在数组中。因此，当我们剩下最后一个元素时，我们需要为最后的猜测加上+1。

[考虑一下n=1的时间可能会更清楚。我们仍然需要1个猜测，但是log_2(1) = 0。因此，我们需要添加+1来修正公式。

[n不是2的幂时，我们可以升到2的下一个更高的幂。对于长度为1000的数组，下一个2的更高的幂是1024，即10。一个1000元素的数组，二进制搜索最多需要11（10 +1）个猜测。

为什么？

[在最坏的情况下，二进制搜索将需要10个步骤来分离剩余的数字，而最后一个步骤则需要检查剩下的唯一一个数字是否是您想要的数字，或者不在数组中。

Answer 2

想象一个大小为8的数组。

l=0, h = 7, mid =  0 + (7-0)/2 = 3   go right
l=4, h = 7, mid =  4 + (7-4)/2 = 5   go right
l=6, h = 7, mid =  6 + (7-6)/2 = 6   go right
l=7, h = 7, mid =  7 + (7-7)/2 = 7   go right  
l=8, h=7 ====> terminates

总比较= 1 + Log 8 = 4