结论
对n个元素进行二分查找，最大比较次数为： ⌊ l o g 2 n ⌋ + 1 \lfloor log_2n \rfloor +1 ⌊log2n⌋+1
问题
给定升序数组，各元素不同，查找某元素。
如果该元素存在：输出该元素的下标
如果不存在该元素，输出-1
算法思路：
- 对于有序数列（从小到大），设定左端l（最小元素下标）和右端r（最大元素下标）
- 当满足条件l <= r时，求中点m，将中点元素的值与所要查找的值比较
- 若中点元素值比所要查找元素小，则应找后半段，所以l = m+1，否则应找前半段r = m - 1
- 重复以上过程，直到找到为止，若l > r，则说明找不到。
代码：
//输入n，输入n个数（升序，各不相同），输入x，求x是第几个数
#include <bits/stdc++.h>
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
k\ge1
k≥1，那么
⌊
l
o
g
2
k
⌋
=
⌊
l
o
g
2
(
k
+
1
)
⌋
\lfloor log_2k\rfloor=\lfloor log_2(k+1)\rfloor
⌊log2k⌋=⌊log2(k+1)⌋
证明：
设x =
⌊
l
o
g
2
k
⌋
\lfloor log_2k\rfloor
⌊log2k⌋，则有
x
≤
l
o
g
2
k
<
x
+
1
x\le log_2k < x+1
x≤log2k<x+1
只需证明
x
≤
l
o
g
2
(
k
+
1
)
<
x
+
1
x \le log_2(k+1) < x+1
x≤log2(k+1)<x+1，即可证明
⌊
l
o
g
2
k
⌋
=
⌊
l
o
g
2
(
k
+
1
)
⌋
\lfloor log_2k\rfloor=\lfloor log_2(k+1)\rfloor
⌊log2k⌋=⌊log2(k+1)⌋
l
o
g
2
k
<
x
+
1
⇒
k
<
2
x
+
1
log_2k < x+1 \Rightarrow k <2^{x+1}
log2k<x+1⇒k<2x+1
由于k和
2
x
+
1
2^{x+1}
2x+1都是整数，所以有
k
+
1
≤
2
x
+
1
k+1\le2^{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+1
k+1<2x+1⇒log2(k+1)<x+1
易知：
x
≤
l
o
g
2
k
<
l
o
g
2
(
k
+
1
)
x \le log_2k <log_2(k+1)
x≤log2k<log2(k+1)
所以
x
≤
l
o
g
2
(
k
+
1
)
<
x
+
1
x \le log_2(k+1) < x+1
x≤log2(k+1)<x+1，该引理得证。
证明对n个元素进行二分查找，最大比较次数为： ⌊ l o g 2 n ⌋ + 1 \lfloor log_2n \rfloor +1 ⌊log2n⌋+1
证明：用数学归纳法
已知n为2时，找第1个元素需要比较1次，找第2个元素需要比较2次，最大查找2次，满足
⌊
l
o
g
2
n
⌋
+
1
\lfloor log_2n \rfloor +1
⌊log2n⌋+1
假设
2
≤
n
≤
k
2\le n\le k
2≤n≤k时，最大查找次数为
⌊
l
o
g
2
k
⌋
+
1
\lfloor log_2k \rfloor +1
⌊log2k⌋+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_2\frac{k+1}{2} \rfloor +1=\lfloor log_2(k+1) \rfloor ⌊log22k+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 + 1 − 1 2 = k 2 \frac{k+1-1}{2}=\frac{k}{2} 2k+1−1=2k，查找这一段的最大查找次数为： ⌊ l o g 2 k 2 ⌋ + 1 = ⌊ l o g 2 k ⌋ \lfloor log_2\frac{k}{2} \rfloor +1=\lfloor log_2k \rfloor ⌊log22k⌋+1=⌊log2k⌋ ，当k+1为奇数即k为偶数时，根据引理1有： ⌊ l o g 2 k ⌋ = ⌊ l o g 2 ( k + 1 ) ⌋ \lfloor log_2k\rfloor=\lfloor log_2(k+1)\rfloor ⌊log2k⌋=⌊log2(k+1)⌋，加上刚刚进行的一次查找，最大查找次数为： ⌊ l o g 2 ( k + 1 ) ⌋ + 1 \lfloor log_2(k+1) \rfloor +1 ⌊log2(k+1)⌋+1
原命题得证。