二分查找的时间复杂度

1. 初探

二分查找的思路，首先和正中间位置的数字比较大小，假如相等，则返回，否则继续从左边或者右边两边查找。

我们先从具体数值看看n次搜索的最大搜索范围。

搜索次数为1时，最多从长度 $L=1$ 的数组中找到目标元素的位置（或者不存在）
搜索次数为2时，最多可以从长度 $L=1 \times 2 + 1 = 3$ 的数组中找到目标
搜索次数为3时，最多可以从长度 $L=3 \times 2 + 1 = 7$ 的数组中找到目标
搜索次数为4时，最多可以从长度 $L=7 \times 2 + 1 = 15$ 的数组中找到目标
搜索次数为5时，最多可以从长度 $L=15 \times 2 + 1 = 31$ 的数组中找到目标
搜索次数为6时，最多可以从长度 $L=31 \times 2 + 1 = 63$ 的数组中找到目标
搜索次数为7时，最多可以从长度 $L=63 \times 2 + 1 = 127$ 的数组中找到目标
……
搜索次数为n时，我们可以猜测通项公式为 $F(n) = 2^n-1$

2. 推导过程

2.1 n次搜索的最大搜索范围

推导过程（非严谨，仅便于理解，待补充高中数列相关知识）：

第1次查找，最多能从长度为1的数组中判断是否存在目标数字。满足 $F(1) = 2^1 - 1$
假定 $n-1$ 次查找公式成立，即 $F(n-1) = 2^{n-1}-1$ 个数中找到目标数字。
假如有 $n$ 次机会，第1次找正中间，剩下的 $n-1$ 次查找最多搜索范围为 $F(n-1)$ 。

F(n) = 2 \times F(n-1) + 1 = 2 \times (2^{n-1}-1) + 1 = 2^n-1 \qquad \qquad 公式（1）

我们来看一下二分查找的高效率。从下表可以看出，对于有序的数组，只要20次即可以从约100万的长度中搜索到目标，30次可以从约10亿的长度中搜索到目标。

n	$2^n$	$2^n-1$
0	1	0
1	2	1
2	4	3
3	8	7
4	16	15
5	32	31
6	64	63
7	128	127
8	256	255
9	512	511
10	1024	1023
20	1,048,576	1,048,575
30	1,073,741,824	1,073,741,823

2.2 搜索范围为L的最多搜索次数

已知 $F(n) = L$ 个数字的搜索范围，反过来求 $n$ ，则由 $n$ 次查找的最大搜索范围 $2^n = L + 1$ ，得：

n= \lceil log_{2}(L+1) \rceil \qquad \qquad 公式（2）

其中 $\lceil x \rceil$ 表示 $x$ 取上整，即不小于 $x$ 的最小整数。

公式切换（这里公式切换较复杂）得：

n = \lfloor log_{2}L \rfloor + 1 \qquad \qquad 公式（3）

结论：

二分查找长度为L的数组，最多查找次数的公式为： $\lfloor log_{2}L \rfloor + 1$ ，其中 $\lfloor x \rfloor$ 表示不大于x的最大整数。
最少查找次数为1。
复杂度一般记为Ο(log n)，这里的log以2为底，n为搜索范围L。

3. 真题练习

1、

【CSP 2019 入门组第一轮 q05】设有100个已排好序的数据元素，采用折半查找时，最大比较次数为（）
A. 7 B. 10 C. 6 D. 8

2、

【NOIP 2009 普及组初赛 q16】有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素：
A. 11次 B. 12次 C. 13次 D. 14次

3、

【NOIP 2008 普及组初赛 q15】对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88，92，100}进行二分查找，成功查找元素19的查找长度（比较次数）是（）。
A. 1 B. 2 C. 3 D. 4

4、

【NOIP 2008 提高组初赛 q10】对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（）。
A. 35/11 B. 34/11
C. 33/11 D. 32/11
E. 34/10