二分查找最大比较次数证明

对n个元素进行二分查找，最大比较次数为： ⌊ l o g 2 n ⌋ + 1 lfloor log_2n rfloor +1 ⌊log2​n⌋+1

给定升序数组，各元素不同，查找某元素。
如果该元素存在：输出该元素的下标
如果不存在该元素，输出-1
算法思路：

对于有序数列（从小到大），设定左端l（最小元素下标）和右端r（最大元素下标）当满足条件l <= r时，求中点m，将中点元素的值与所要查找的值比较若中点元素值比所要查找元素小，则应找后半段，所以l = m+1，否则应找前半段r = m - 1重复以上过程，直到找到为止，若l > r，则说明找不到。
代码：

//输入n，输入n个数（升序，各不相同），输入x，求x是第几个数 
#include 
using namespace std;
int main()
{
    int n, a[1005], x, l, r, m;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    cin >> x;
    l = 1, r = n;
    while(l <= r)//l在r左边 
    {
        m = (l + r) / 2;//取中点位置 
        if(x > a[m])//如果x在右半部分 
            l = m + 1;//l移到中点右边 
        else if(x < a[m])//如果x在左半部分 
            r = m - 1;//r移到中点左边 
        else
        {
            cout << m;//如果中点是要查找的数字，那么输出该位置 
            return 0;
        }
    }
    cout << -1;//没找到，输出-1 
    return 0;
}

按上述算法进行二分查找，证明二分查找的最大查找次数
引理1：如果k为偶数，且 k ≥ 1 kge1 k≥1，那么 ⌊ l o g 2 k ⌋ = ⌊ l o g 2 ( k + 1 ) ⌋ lfloor log_2krfloor=lfloor log_2(k+1)rfloor ⌊log2​k⌋=⌊log2​(k+1)⌋
证明：
设x = ⌊ l o g 2 k ⌋ lfloor log_2krfloor ⌊log2​k⌋，则有 x ≤ l o g 2 k < x + 1 xle log_2k < x+1 x≤log2​k 只需证明 x ≤ l o g 2 ( k + 1 ) < x + 1 x le log_2(k+1) < x+1 x≤log2​(k+1)

l o g 2 k < x + 1 ⇒ k < 2 x + 1 log_2k < x+1 Rightarrow k <2^{x+1} log2​k 由于k和 2 x + 1 2^{x+1} 2x+1都是整数，所以有 k + 1 ≤ 2 x + 1 k+1le2^{x+1} k+1≤2x+1
而k是偶数，k+1是奇数， 2 x + 1 2^{x+1} 2x+1一定是偶数，所以不可能满足 k + 1 = 2 x + 1 k+1=2^{x+1} k+1=2x+1
所以有 k + 1 < 2 x + 1 ⇒ l o g 2 ( k + 1 ) < x + 1 k+1<2^{x+1} Rightarrow log_2(k+1) 易知： x ≤ l o g 2 k < l o g 2 ( k + 1 ) x le log_2k 所以 x ≤ l o g 2 ( k + 1 ) < x + 1 x le log_2(k+1) < x+1 x≤log2​(k+1) 证明对n个元素进行二分查找，最大比较次数为： ⌊ l o g 2 n ⌋ + 1 lfloor log_2n rfloor +1 ⌊log2​n⌋+1

证明：用数学归纳法
已知n为2时，找第1个元素需要比较1次，找第2个元素需要比较2次，最大查找2次，满足 ⌊ l o g 2 n ⌋ + 1 lfloor log_2n rfloor +1 ⌊log2​n⌋+1
假设 2 ≤ n ≤ k 2le nle k 2≤n≤k时，最大查找次数为 ⌊ l o g 2 k ⌋ + 1 lfloor log_2k rfloor +1 ⌊log2​k⌋+1，证明：n为k+1时最大查找次数为 ⌊ l o g 2 ( k + 1 ) ⌋ + 1 lfloor log_2(k+1) rfloor +1 ⌊log2​(k+1)⌋+1
n = k + 1 n=k+1 n=k+1时，进行一次二分查找后，下一次要查找的长度为：

如果k+1为偶数，下一次查找的长度为 k + 1 2 frac{k+1}{2} 2k+1​，查找这一段的最大查找次数为 ⌊ l o g 2 k + 1 2 ⌋ + 1 = ⌊ l o g 2 ( k + 1 ) ⌋ lfloor log_2frac{k+1}{2} rfloor +1=lfloor log_2(k+1) rfloor ⌊log2​2k+1​⌋+1=⌊log2​(k+1)⌋，加上刚刚进行的一次查找，最大查找次数为： ⌊ l o g 2 ( k + 1 ) ⌋ + 1 lfloor log_2(k+1) rfloor +1 ⌊log2​(k+1)⌋+1如果k+1为奇数，下一次查找的长度为k/2，查找这一段的最大查找次数为： ⌊ l o g 2 k 2 ⌋ + 1 = ⌊ l o g 2 k ⌋ lfloor log_2frac{k}{2} rfloor +1=lfloor log_2k rfloor ⌊log2​2k​⌋+1=⌊log2​k⌋ ，当k+1为奇数即k为偶数时，根据引理1有： ⌊ l o g 2 k ⌋ = ⌊ l o g 2 ( k + 1 ) ⌋ lfloor log_2krfloor=lfloor log_2(k+1)rfloor ⌊log2​k⌋=⌊log2​(k+1)⌋，加上刚刚进行的一次查找，最大查找次数为： ⌊ l o g 2 ( k + 1 ) ⌋ + 1 lfloor log_2(k+1) rfloor +1 ⌊log2​(k+1)⌋+1