二分查找的时间复杂度及其不足

2020-09-25

从二分查找开始

上一篇博客《从零开始的数据结构之向量》具体实现了基于有序向量的二分查找，即如下代码段：

template <typename T>
Rank vector<T>::search(T const & e,Rank lo,Rank hi)         //二分查找 
{
int mi;
while(lo<hi)                                            //将递归改为迭代 
{
	mi=(lo+hi)>>1;
	if(e<_elem[mi]) hi=mi;
	else if(e>_elem[mi]) lo=mi+1;
	else return mi;
 } 
 return -1;                                            //查找失败 
}

在以上查找中，所花费的时间主要分为两类：元素的大小比较、秩的算术运算及其赋值。为基本数据类型时，二者的复杂度均为,然而元素的秩无非是整数，当变化时，情形可能截然不同，甚至大小比较无法在时间内完成。因此，接下来引入“查找长度”的概念。

查找长度

我们规定在一次查找中，所经历的大小比较次数为其查找长度。为了估计出一般情形下的成功查找长度，不失一般性地在等概率条件下考察长度为的有序向量，并将平均查找长度记为，总和记为。
当时，有边界条件：
接下来用递推分析法。对于长度为的有序向量，每一步迭代都有三种可能的分支：

经过次成功的比较，转化为一个规模为的新问题
经过次失败的比较和次成功的比较，转化为另一个规模为的新问题
经过次失败的比较，在当前位置命中
由以上分析可得递推式：
$C(k)=[C(k-1)+(2^{k-1}-1)]+[2*(2^{k-1}-1)+C(k-1)]+2 \\ =2*C(k-1)+3*2^{k-1}-1$
令
则有：
$F(1)=-2 \\ F(k)=2*F(k-1)=2^{k-1}*F(1)=-2^{k}$
可得：

所以：
$C_{average}(k)=C(k)/(2^{k}-1) \\ =3k/2-1+\mathcal{O}(\varepsilon)$
也就是说，忽略末尾的波动项，可得平均查找长度为：
$\mathcal{O}(1.5*k)=\mathcal{O}(1.5*log_{2}n)$
不足
尽管二分查找算法即使在最坏的情况下也可以保证的渐进复杂度，但就其常系数而言仍有改进余地。以成功查找为例，即使是迭代次数相同的情况，对应的查找长度也不尽相等。究其根源在于，在每一步迭代中为确定左、右分支方向，分别需要做次或次元素比较，从而造成不同情况所对应查找长度的不均衡。