二分查找的最大比较次数

二分查找很简单，可是对于一个区间长度为n的数组，最大的比较次数为多少呢？

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

如果区间长度为1，显然最多比较1次
区间长度为2，最多比较2次（[0,2) -> [0,1) -> [0,0)）
区间长度为3，最多比较2次（[0,3) -> [0,1) [2,3)）
区间长度为4，最多比较3次（[0,4) -> [0,2) -> [0,1)）

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

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

假设对于区间长度为2^(k-1) ~ 2^k-1的区间，最多比较k次
则对于区间长度为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次