数据结构与算法（3）有序向量

唯一化

有序向量是相对于无序向量而言，无序向量要求元素之间至少应该能比较是否相等，我们称作比对操作；而有序向量更为复杂，它需要能够判定任何一对元素孰大孰小，这叫作比较操作。元素之间可以相互比较只是有序向量的一个必要条件，如果要成为一个真正的有序向量，还必须要求其中的元素确实是按照顺序排列的，因此就存在一个如何甄别一个向量是否有序的问题。

有序性及其甄别

• 与起泡排序算法的理解相同：

​ 有序序列中，任意一对相邻元素顺序；无序序列中，总有一对相邻元素逆序。

• 因此，逆序相邻元素的数目，可用以度量向量的逆序程度。
• 无序向量经预处理转换为有序向量之后，相关算法多可优化。

template <typename T>  //返回逆序相邻元素对的总数
int Vector<T>::disordered() const {
	int n = 0;    //计数器
	for (int i = 1; i < _sizei++)        //逐一检查各对相邻元素
		n += (_elem[i - 1] > _elem[i]);  //逆序则计数
	return n;   //向量有序当且仅当 n = 0
}  //若只需判断是否有序，则首次遇到逆序对之后，即可立即终止

根据上面的分析可以知道，一个向量是有序的，当且仅当经过disordered()判断以后返回的值是零。实际上只要向量中的元素本身是支持大小比较的，就有一定的办法将它转化为有序向量。其中的原因在于经过这样的一个转换以后虽然我们花费了一定的成本，但此后涉及到的很多操作也就是相关算法，大多都可以优化，相应地所得要远远比转换时所花费的成本大的多。

低效算法

上一篇文章介绍了无序向量的去重操作，现在我们希望把这种去重操作推广到有序向量，即将一个有序向量中的重复元素（如果存在）全部剔除掉，同样地每一组重复元素只保留一个副本。有序向量其实相对于无序向量而言，具有更好的规范性。这种规范性是指在有序向量中，彼此重复的元素必然会依次相互紧邻地构成一个一个的区间，比如就下图中的例子而言，这些元素相互重复，它们彼此紧邻，会紧密地排列成一个区间，其它元素也有这种规律。所以既然我们需要从每一组元素中保留一个副本，等价于从其中找出一个代表并且保留下来。

具体到一个算法，可以大致用一个线性扫描过程来描述：每次都观察并比对一对相邻的元素，如果二者相等就将后者删除掉，并且继续比较，如果后者还相等就把它继续删除掉，直到遇到一个不相重复的元素，这个时候我们才把注意力后移，再去考虑下一对紧邻的元素，如果依然出现这种情况再删除，直到又转到下一对。这样确实可以顺利地把所有重复的元素都剔除掉，但是不倾向与使用，因为其效率低。

template <typename T>
int Vector<T>::uniquify() {
	int oldSize = _size;  int i = 0;  //从首元素开始
	while (i < _size - 1)  //从前向后，逐一比对各相邻元素
		//若雷同，则删除后者；否则，转至后一个元素
		(_elem[i] == _elem[i + 1]) ? remove(i + 1) : i++;
	return oldSize - _size;  //返回向量规模变化量，即删除元素总数
}   //注意：其中_size的减小，由remove()内隐式地完成

低效算法的复杂度

• 算法的运行时间主要取决去while循环，次数共计: _size - 1 = n -1
• 最坏情况下：每次都需调用remove()，耗时$O(n-1)\sim O(1)$，累计$O(n^2)$

​ 尽管省去fine()，总体竟与无序向量的deduplicate()相同。

高效算法

需要首先对原有的算法进行反思，我们发现造成低效率的根源在于：其中的同一个元素有可能会作为被删除元素的后继，而多次地参与前移操作，对于这样的一个元素来说虽然它每次都是向前移动，但是很可惜它的每一次移动只会移动一个单元，而不是一次性地一步到达它最终的位置。

反过来这就启示我们，如果能够将每一个重复的区间作为一个整体来考虑，成批地删除雷同的元素而不是像刚才那样逐个地去删除，并且逐个地移动，就有可能实现这种一步到位式的移动，从而使得整体的性能大大地改进。

这个新算法的思路可以由上面的图来表示，在任何时刻我们关注的都是i和j两个元素，而且这里有一个不变性，也就是在i之后 j之前的所有这些元素都与i重复，这个算法一直扫描直到发现第一个与i不同的元素。如果它确实是不同的话我们就只需将j向前移到与i紧邻于右侧的这个位置，这是一个很高明的删除算法，因为在这样的一个过程中虽然没有显式地去做这些重复元素的删除，但是实际上已经无形中将它们忽略掉了，等效于做删除。

template <typename T>
int Vector<T>::uniquify() {
	Rank i = 0, j = 0;     //各对互异“相邻”元素的秩
	while (++j < _size)    //逐一扫描，直至末元素
		//跳过雷同者；发现不同元素时，向前移至紧邻于前者右侧
		if (_elem[i] != _elem[j])  
			_elem[++i] = _elem[j];
	_size = ++i;  
	shrink();      //直接截除尾部多余元素
	return j - i;  //向量规模变化量，即被删除元素总数
}   //注意：通过remove(lo,hi)批量删除，依然不能达到高效率

高效算法的复杂度

下面通过一个例子来分析新算法的复杂度：

• 共计n-1次迭代，每次常数时间，累计$O(n)$时间。

算法首先考虑的i和j元素，其实就是0和1号元素，对这个例子而言它们是彼此重复的元素，所以在那个循环中将会通过那个隐藏着看不见的else直接将它忽略掉，并且使得j进而转向下一个单元，以及在接下来的一个循环中再下一个单元，以及再下一个单元。执行到3和5出现了第一次的不同，按照刚才算法的逻辑会把i++到1号位置，然后把第j号元素取出来复制到对应的1号位置上，这就是为什么变成了3和5相邻。注意，在这个过程中我们并没有做显式的删除操作。

接下来的操作与之类似，直到j第一次越过右侧的边界的时候循环退出，算法也就终止。这个时候我们已经无形中将后边的这些元素统一地给删除掉了，这种删除非常的高明，因为我们没有做任何的一次显式的删除操作，而只是通过合理的计算得知了最终的向量规模之后，对_size这个量重新进行了一次设置。

通过这个例子可以得出，算法过程中只是经过了i+1次的迭代，每次移动j必然总是会往后移动一位。而且在每一次过程中，所做的操作无非就是一次比对，只有在比对不同的情况下才会做一次复制，即便是最坏的情况下既比对而且也复制的话，累计起来也不过是常数的时间。所以换而言之，整个这个新的算法只需要$O(n)$线性的时间。

二分查找（版本A）

在上一篇文章中介绍了无序向量的查找算法，它的格式为Vector::find(e, lo, hi)，第一个参数指明查找的对象，第二和第三个参数lo和hi指示查找的区间范围。这种算法从思路上来说大体是从一端出发不断地逐个比对，直到发现某一个特定的元素就是e，或者一直到lo-1这个位置在左侧越界，即是查找失败。所以最好情况它只需$O(1)$的时间，但是从最坏的情况以及从一般e的概率分布的平均情况而言，都不得不需要线性的时间。

那么在进入有序向量之后，我们应该可以得到更快的一种解决方案，不妨重新起一个名字叫search()，以示与无序向量的那个find()的区别。当然从操作的参数以及接口的语义来说都是类似的，即我们同样要在lo到hi这样一个左闭右开的区间里找到一个特定的元素。

统一接口

template <typename T>   //查找算法统一接口，0 <= lo < hi <= _size
Rank Vector<T>::search(T const& e, Rank lo, Rank hi) const{   
	return(rand() % 2) ?   //按各50%的概率随机选用
		binSearch(_elem, e, lo, hi)   //二分查找算法，或者
	  : fibSearch(_elem, e, lo, hi);  //Fibonacci查找算法
}

这里所提供的search()接口从形式上看是统一的，即ADT。从内部讲，它的具体实现算法却不见得完全一样，后面的的各节将会分别介绍二分查找算法以及Fibonacci查找算法，而且对每一种算法都有不同的版本。

为了做测试这里采用了一个随机的方法，也就是在0和1之间随机地取一个数，从而随机地调用这两个算法。在实际应用中可以针对不同的情况在这几种算法中选择其一。

seach()的简要的操作语义就是在lo和hi所确定的这个区间找出目标元素e（如果它确实存在的话）。这里需要处理很多特殊的情况，比如，目标元素并不存在与规定的区间中，这就叫失败。在此前学习的无序向量的find的接口中我们只是简单地返回了一个标志-1，但严格地说这样做是不够的。反过来有可能目标元素存在多个，既然作为有序向量，一旦有多个e的话，那么它肯定会连续地分布构成一个区间。在这种情况下，到底是返回最前边的一个，最后的一个？还是中间的某一个？这些都是我们需要进一步地从语义上予以约定的。

语义约定

在语义上的细致约定是非常有必要的，否则search()接口将只能作为一个孤立的功能，而不能有效地、便捷地为其它的算法，作为一个基本的部件而利用。search()接口至少应该使得有序向量自身的动态维护变得非常便利，比如在有序向量不断插入元素过程中，我们希望往往能够采用这样一种形式：当插入某一个元素时，首先要通过search()来确定一个适当的位置，例如查找返回的那个值再加1，然后再将e插入于这个秩所对应位置，并且同时使得这个有序向量继续是一个有序向量。

V.insert(1 + V.search(e), e);

幸运的是前人已经帮我们设计出了这样的语义约定，比如下面就是其中的一种约定：

• 在有序向量区间V[lo, hi)中，确定不大于e的最后一个元素
• -∞ < e < V[lo] 时，返回 lo-1 （左侧哨兵）
• V[hi-1] < e < +∞ 时，返回hi-1（右侧哨兵的前一个）

按照这个约定，对于要查找的元素有重复元素的情况，即有多个元素是与目标的元素是重复的，应该返回的所谓的不大于e的最后一个元素，也就是这个区段的右端点。如果我们要做一个插入，把新的元素插入这个位置同加1后的位置，即重复元素区间右端点的后面，正是再合适不过的。

这里的合适是指：第一，它继续保持了整体的有序性；第二，它以及与它雷同的那些元素会保持它们插入到这个向量中的先后的次序。所以这种语义约定是非常好的，它涵盖了我们几乎所有的情况包括特殊情况。所以接下来我们在实现这些具体的算法的时候，必须最终落实到能够符合这种语义的要求。

原理

这个版本只是为了说明原理，从严格的意义上讲，它还不能完全地符合刚才的语义要求，在后面的小节就会对它进行改进。

• 减而治之：以任一元素x = S[mi] 为界，都可将待查找的区间分为三部分

  S[lo, mi) <= S[mi] <= S(mi, hi) // S[mi] 称作轴点

• 只需将目标元素e与x做比较，即可分三种情况进一步处理：

  • e < x：则e若存在，必属于左侧子区间S[lo, mi)，故可递归深入
  • x > e：则e若存在，必属于右侧子区间S(mi, hi)，亦可递归深入
  • x = e：已在此处命中，可随即返回 //若有多个，返回哪个？后面会介绍

• 二分（折半）策略：轴点mi总是取作中点（至少能保证不是最坏情况）

  于是每经过至多两次比较，或者能够命中，或者将问题规模减一半

实现

template <typename T>   //在有序向量区间[lo, hi)内查找元素e
static Rank binSearch(T* A, T const& e, Rank lo, Rank hi) {
	while (lo < hi) {  
		Rank mi = (lo + hi) >> 1;     //每步迭代可能要做两次比较判断，有三个分支
		if      (e < A[mi])  hi = mi;      //深入前半段[lo, hi)继续查找
		else if (A[mi] < e)  lo = mi + 1;  //深入后半段(mi, hi)
		else                 return mi;    //在mi处命中
	}
	return -1;   //查找失败
}

Tips：这里有编写程序的一个小的习惯，可以帮助我们更好地思考问题并且写出算法，更重要的是可以让代码更加好理解，同时也减少一些不必要的失误。我们这里统一地都用了小于号，因为小于号的左右的次序和我们通常所画的这样从小到大的次序是吻合的，所以这里e < A[mi]的解读既可以认为是e小于mi，也可以认为是e存在于当前这个分界点mi的左侧。当这样顺着读下来时，当然我们就应该深入到前半段也就是左半段去，相应地呢，我们应该修改右侧的界桩hi = mi。同样接下来A[mi] < e解读也是这样与其说是mi小于e，不如更直观地说是我们的目标e是处于mi这个分界点的右侧，所以我们应该深入到右半段也就是后半段去继续搜索，相应的操作也就是去修改左侧的界桩lo = mi +1。

实例与复杂度

• S.search(8, 0, 7)：共经$2+1+2=5$次比较，在S[4]处命中

• S.search(3, 0, 7)：共经$1+1+2=4$次比较，在S[1]处失败

• 线性递归：$T(n)=T(n/2)+O(1)=O(logn)$，大大优于顺序查找

  递归跟踪：轴点总取重点，递归深度$O(logn)$；各递归实例均耗时$O(1)$。

查找长度

有序向量的查找是一种非常基本的算法，而且它存在多个版本，因此除了上面利用渐近的复杂度能够从总体上把握它的大体性能以外，我们还需要对不同版本算法的性能做更加细微的评定。具体来说就是考察渐近复杂度$logn$前面的那个常系数，而具体地在统计和分析的时候，更多的是考量关键码的比较操作次数，也就是在其中所执行的if语句的次数，我们将此称作是不同的算法在不同的情况下所对应的查找长度。

• 如何更为精确地评估查找算法的性能？

  考查关键码的比价次数，即查找长度（search length）

• 通常，需分别针对成功与失败查找，从最好，最坏，平均等角度评估

• 例如，成功、失败时的平均查找长度均大致为$O(1.50\cdot logn)$。

下面是一个一个具体的实例，这是一个由七个元素构成的有序向量，其实它的数值是具体是多少我们并不在意，只要它是非降排列的就可以。如果把算法改写成递归的形式，那么整个的不同情况的递归跟踪将构成下面的递归跟踪图，每条虚线旁边的数字代表由上一步执行到下一步所增加的比较操作的次数，具体位置的方框中的数字代表查找到它所需要总的比较操作次数，即查找长度。需要注意的是，每次递归到左子区间，比较操作次数增加1，而递归到右区间，比较操作次数增加2。

• n = 7时，各元素对应的成功查找长度为$\{4,3,5,2,5,4,6\}$

​ 在等概率情况下，平均成功查找长度$=29/7=4.14$；

• 共有8中失败情况，查找长度分别为$\{3,4,4,5,4,5,5,6\}$

  在等概率情况下，平均失败查找长度$=36/8=4.50$；

• 可见，成功和失败的平均查找长度大致是$1.50\cdot log_28$

Fibonacci查找

改进思路及原理

在上一节引入了二分查找（Binary search）这样的一个概念，并且给出了一个基本的算法的版本，这个版本的复杂度从渐近意义而言应该是logn量级的，但如果进一步地细微地来考察前面的系数大致是1.5，我们也指出这个1.5是可以改进的。我们现在就来看看，如何通过一种新的算法：fibonacci查找（fibonaccian search）来对此进行改进。

上一节的末尾以一个长度为7的有序向量为例，具体地给出了在成功和失败情况下平均查找长度的估算的过程。实际上通过那个实例的推而广之，如果考虑更一般的情况，不难发现此前所介绍的版本A，确实还有很大地改进余地。这样一个判断是来自于这样一个观察事实，也就是说版本A这个算法实际上从用意上讲，它是试图通过使各种情况的搜索在迭代次数上的平衡来尽可能地回避掉最坏的情况。

具体讲比如所有的失败情况大部分都会失败在同样深度的，也就是最深的这个位置，所以它表面上看是平衡的，但这其中却蕴涵着很大的不平衡。因为在整个这个查找的过程中我们在任何一个位置上，如果要决定是向左或者是向右深入的话，所花费的成本，也就是比较的次数是不等的。准确地说按照版本A，向左侧只需要一次比较，而向右侧却需要两次比较，所以这样一个表面上看是非常公平的一个平衡，实际上在内部却蕴涵着极大的不平衡，所以我们确实有理由怀疑算法的效率是否已经达到最优。

反过来我们也可以得到改进的一个思路，具体讲就是既然我们已经看到目前的机制中，向左侧确实会成本更低，而向右侧更高。那么为什么不把这个搜索的各种情况画成类似下面的这样一个树状图，做成左侧是更深的，而右侧是相对更浅的。这样一个表面上看的不平衡，却因为它恰好和这种成本互相之间能做一个合适的补偿，反过来有可能从整体上会得到更优，也就是说使得整体的查找平均长度反而会缩短。

具体来讲，越是成本低的转向我们就越希望更多地做，越是成本更高的越是希望它能更少地来做，所以这样的话我们就得到了新的算法的改进的思路。那么具体这个思路怎么来兑现呢？非常有意思的是需要用到fibonacci数。不失一般性，假设有序向量的长度N，就是某个fibonacci数减1的形式。

如下图所示有序向量的长度n = fib(k) - 1，那我们就在其中选择这么样一个特定的切分点mi，mi = fib(k-1) - 1，如果以这个点为切分，那么左边子向量的长度就恰好是fib(k-1) - 1，而右边子向量的长度恰巧是
fib(k-2) - 1。可见这样一种切分的好处就是，在任何时候只要按照这样来切分，无论是向左还是向右它都会从长度上保持某个fibonacci数再减1的形式，而这种形式实际上恰好是最优的。

实现

首先定义一个Fib类，让其提供一些接口。

class Fib { //Fibonacci数列类
private:
  int f, g; //f = fib(k - 1), g = fib(k)。均为int型，很快就会数值溢出
public:
  Fib ( int n ) //初始化为不小于n的最小Fibonacci项
  { f = 1; g = 0; while ( g < n ) next(); } //fib(-1), fib(0)，O(log_phi(n))时间
  int get()  { return g; } //获取当前Fibonacci项，O(1)时间
  int next() { g += f; f = g - f; return g; } //转至下一Fibonacci项，O(1)时间
  int prev() { f = g - f; g -= f; return g; } //转至上一Fibonacci项，O(1)时间
};

Fibonacci查找可以实现为下面的一段代码，可以注意到它的接口还是完全一样的，而且在其中的这个循环，大致来说也是与版本A类似的，即每次都要来判断以保证当前的lo和hi构成一个合法的区间，如果这个区间能够收缩到非法(lo == hi)，那也就意味着查找是失败的，这跟此前的版本A是一样的。

#include "fibonacci/Fib.h" //引入Fib数列类
// Fibonacci查找算法（版本A）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
template <typename T> 
static Rank fibSearch ( T* S, T const& e, Rank lo, Rank hi ) {
 
   Fib fib(hi - lo);   //用O(log_phi(n = hi - lo)时间创建Fib数列
   while(lo < hi) {
      while ( hi - lo < fib.get() ) fib.prev();   //自后向前顺序查找（分摊O(1)）
      Rank mi = lo + fib.get() - 1;       //确定形如Fib(k) - 1的轴点
      if      ( e < S[mi] ) hi = mi;      //深入前半段[lo, mi)继续查找
      else if ( S[mi] < e ) lo = mi + 1;  //深入后半段(mi, hi)继续查找
      else                  return mi;    //在mi处命中
   } //成功查找可以提前终止
   return -1; //查找失败
} //有多个命中元素时，不能保证返回秩最大者；失败时，简单地返回-1，而不能指示失败的位置

查找长度

• fibonacci查找算法的平均查找长度为$O(1.44 \cdot logn)$，略优于二分查找
• 仍以n = fib(6) -1 = 7 为例，在等概率情况下：
  • 平均成功查找长度$=(2+3+4+4+5+5+5)/7=28/7=4.00<4.14$
  • 平均失败查找长度$=(4+5+4+4+5+4+5+4)/7=35/7=4.38<4.50$

最优性

• 通用策略：对于任何的A[0, n)，总是选取A[λn]作为轴点，$0\le \lambda <1$:

  比如二分查找对应于$\lambda=0.5$，Fibonacci查找对应于$\lambda=\phi=(\sqrt{5}-1)/2=0.6180339\dots$（黄金分割比）

• 在[0, 1)内，$\lambda$如何取值才能达到最优？设平均查找长度为$\alpha(\lambda)\cdot log_2n$，何时$\alpha(\lambda)$最小？

• 递推式：$\alpha(\lambda)\cdot log_2 n=\lambda\cdot [1+\alpha(\lambda)\cdot log_2 (\lambda n)]+(1-\lambda)\cdot [2+\alpha(\lambda)\cdot log_2 \left((1-\lambda) n \right)]$

• 整理后：$\frac{-ln2}{\alpha(\lambda)}=\frac{\lambda\cdot ln\lambda+(1-\lambda)\cdot ln(1-\lambda)}{2-\lambda}$，当$\lambda=\phi$时，$\alpha(\lambda)=1.440420\dots$达到最小。

相对于我们上一节的二分查找$\alpha(\lambda)=1.50$，Fabonacci查找又有了一定的改进，而且从本节的分析可以看出这种改进已经达到了极限，如果我们不再改变这个算法的总体模式和框架的话。

二分查找（改进）

这一节将介绍另一种思路的改进，这是一种直截了当的改进思路，既然我们已经注意到了此前的版本A中造成效率略低的原因是因为左右分支的转向代价不平衡，那么可以考虑是否能将二者做成是平衡的。

改进思路

• 二分查找中左、右分支转向代价不平衡的问题，也可直接解决

• 比如，每次迭代（或每个递归实例）仅做1次关键码比较，如此，所有分支只有2个方向，而不再是3个

• 同样地，轴点mi取作中点，则查找每深入一层，问题规模也缩减一半

  1）e < x： 则e若存在，必属于左侧子空间S[lo, mi)，故可递归深入

  2）x <= e：则e若存在，必属于右侧子空间S[mi, hi)，亦可递归深入

• 只有当元素数目hi - lo = 1时，才判断该元素是否命中，这是该算法做出的牺牲

版本B：实现

主要注意代码中与版本A不同的地方。

// 二分查找算法（改进）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo < hi <= _size
template <typename T> 
static Rank binSearch ( T* S, T const& e, Rank lo, Rank hi ) {
  while ( 1 < hi - lo ) {         //每步迭代仅需做一次比较判断，有两个分支；成功查找不能提前终止
    Rank mi = ( lo + hi ) >> 1;   //以中点为轴点（区间宽度的折半，等效于宽度之数值表示的右移）
    ( e < S[mi] ) ? hi = mi : lo = mi;     //经比较后确定深入[lo, mi)或[mi, hi)
  }    //出口时hi = lo + 1，查找区间仅含一个元素A[lo]
  return (e == A[lo]) ? lo : -1; //返回命中元素的秩或者-1
}

这个算法是封闭的，可以运转，而且可以完全实现此前一样的功能。与此前的版本A对比，它在最好情况下反而有所倒退，原因是在与即使是成功的情况它也一直要推迟到最终，只有在经过最终的这次比对之后才会确定是否成功。此前的版本A它的最好情况是非常好的，最最好的情况莫过于在第一次试图做减而治之的时候，所采用的那个切分点就成功命中，只需要$O(1)$的时间。

本节改进的二分查找无论如何都一直要切分到最后，所以最好的情况的时间复杂度是$O(logn)$。但是反过来最坏的情况又会更好，因为我们这里最坏的情况不会出现每一次都是向右，即每次都要花费两次比较的情况，所以最坏的情况会得到抑制。所以从总体而言此前的那个版本A如果说它在性能上好坏情况相差非常大的话，那么本节中改进的版本在整体性能上，它就会趋于更加的稳定，即差异化不是那么大，当然这还不是它的最大的优势所在。

语义约定

• 以上的二分查找及Fibonacci查找算法，均未严格地兑现search()接口的语义约定：

  返回不大于e的最后一个元素

• 只有兑现这一约定，才可以有效支持相关算法，比如：V.insert(1 + V.search(e), e)

  1）当有多个命中元素时，必须返回最靠右（秩最大）者

  2）失败时，应返回小于e的最大者（含哨兵lo-1）

版本C：实现

在刚才代码的基础上，我们做进一步的调整，得到一个最终的版本，它可以严格地实现上面定义的语义。

template <typename T> static Rank binSearch ( T* S, T const& e, Rank lo, Rank hi ) {
  while ( lo < hi ) 
  {   //不变性：A[0,lo) <= e < A[hi,n)
    Rank mi = ( lo + hi ) >> 1;    //以中点为轴点
    ( e < S[mi] ) ? hi = mi : lo = mi + 1;    //经比较后确定深入[lo, mi)或(mi, hi)
  } //出口时，A[lo = hi]为大于e的最小元素
  return --lo;   //故循环结束时lo - 1即不大于e的元素的最大秩
}   //有多个命中元素时，总能保证返回秩最大者；查找失败时，能够返回失败的位置

就算法的结构而言，这个新的算法版本C和此前的版本A，尤其是版本B，似乎没有什么太大的区别。解读一下：当这个区间还是合法之前我们就不断地迭代，每一次也照样是取出它的中点作为轴点，并且经过一次比较从而决定到底是向左侧还是向右侧深入，那么直到区间宽度缩小到足够小的时候，才返回最终的值。

需要注意的是版本C和版本B，虽然在功能上是等效的，但是在很多细节上却有着本质的区别：

• 待查找区间宽度缩短至0而非1时，算法才结束
• 转入右侧子向量时，左边界取作mi+1，而非mi //A[mi]会被遗漏？下一小节证明
• 无论成功与否，返回的秩严格符合接口的语义约定

正确性

首先通过下面的图例来具体地了解一下版本C的工作过程，其实最主要的是它的每次迭代的过程都是类似的。如图(a)，在整个向量的区间内，我们关注的是某一个特定的从lo到hi的一个查找区间，每次在这个区间里都要考虑middle point，即图中的x。

我们以它为界，经过一次比较以后有可能会发现目标元素更小所以就深入到如图b所示的左侧的这个子区间；或者对称地，因为目标元素更大而深入到右侧的这个区间，如图(c)。版本C的算法中左侧子区间和右侧的子区间都没有覆盖这个middle point，而且对middle point也没有做显式地判断，所以这也是为什么有理由怀疑它有可能是这个算法的一个疏忽。

接下来我们来证明这样一个模式实际上是安全的，为此同样用我们的两种技巧：第一就是给出这个算法的不变性
其次要给出它的一个单调性，而单调性是一目了然，就不再说明了，主要是证明它的不变性：

• 不变性：A[0, lo) <= e < A[hi, n) //A[hi] 总是大于e的最小者
• 初始时，lo = 0且 hi = n，A[0, lo) = A[hi, n) = $\varnothing$，自然成立
• 数学归纳法：假设不变性一直保持至图(a)的状态，下一步无非两种情况：

第一种情况，也就是深入左侧这个分支的情况，即图(b)。那么此前的判断e < A[mi]返回的是True，之后执行 hi = mi，从而使得右侧的这段区间向左拓展是安全的，因为确实可以断定这个整个区间内的这些元素都是严格地大于e的，因为它们其中最小的那个元素也就是A[mi]都大于e。而A[0, lo)保持不变,所以这种情况是没有问题的。

第二种情况，也就是深入右侧这个分支的情况，即图(c)。那么此前的判断e < A[mi]返回的是False，之后执行 lo = mi，此时e是不小于A[mi]的，而A[mi]元素是左段区间中最大的，所以左段区间都是都是不大于e的。这样一个左侧区间向右拓展的动作在刚才不变性的意义上讲，依然是安全的，它使得不变性得到了延续。所以经过一次迭代以后无论是向左还是向右的深入，不变性都是成立的。

• 单调性：显而易见，直到最后会出现一个情况，就是整个区间的宽度变成零，可以表示为下图。

从整个的原始的搜索空间开始，经过不断地压缩、压缩、压缩之后，将搜索的范围缩小到一个宽度为零的一个区间，其实它就只是一个分界。它严格地将整个区间分为了左右两部分，由不变性左侧这部分依然是不大于e，而右侧这部分是严格地>e。如果查找的结果是命中的，我们只需要返回左侧这个区间的最右端的那个元素就可以了，而这个元素正是A[lo-1]。这也就是为什么我们在算法的最终返回之前要做一次--lo的操作。

这样的话我们就得到了一个从功能上、从语义上、从性能上都近乎完美的算法！

插值插值

插值查找（Interpolation Search）有序向量查找算法的一个另类的变种，此前所介绍的Fibonacci search或binary search包括它们的各种版本对向量只做了一个假定，即其中的元素是单调有序的，对于其中元素的分布情况并没有做任何的假设，也就是可以是完全理想任意随机的。但是在某些情况下也许不是这样，比如我们可能不仅知道向量是有序的，而且其中的元素是按照某种先验规律随机分布的。

在这里我们考虑一种最常见的随机分布：均匀独立的随机分布，比如在从lo一直到hi的秩的范围之内，所有的元素都是互相不影响，各自独立的，然后从取值来看是均匀的取自于某一个区间范围。如果我们确实知道诸如此类的规律的话，就有可能实现优于此前那些算法$O(logn)$的更高的查找效率，以$o(logn)$的效率来完成一次查找。

原理与算法

在均匀且独立的随机分布下，所有的元素在排序之后，即组织成一个有序向量之后，必然大体上是按线性增长的趋势分布的，从最小值lo开始大致是线性增长到最高值hi。这就意味着对于其中的任何一个潜在元素mi，都可以写出这样一个近似的线性等式，它们的秩的比与它们的数值比，二者是近似接近的。

$$\frac{mi-lo}{hi-lo}\approx \frac{e-A[lo]}{A[hi]-A[lo]}$$

实际上这给了我们一个启示，即在每次确定mi的时候，既不需要固定的用1/2，也不需要固定的用小写的φ（黄金分割比），甚至不需要用某一个一般的λ，而是可以动态的来猜测这样一个轴点，就是根据上面的等式。将这个等式稍微整理一下把mi提到左侧，我们就可以知道根据lo、hi以及它们对应的这两个元素的数值，以及每次动态要查找的那个元素的数值e，就可以大致的估算出mi，这样的话如果整个的减而治之的搜索过程可以认为是一个不断收缩包围圈逐步收敛的一个过程，那么它将会使得收敛的速度极大的加快，从而更快速的完成我们整个的查找。

$$mi\approx lo+(hi-lo)\cdot \frac{e-A[lo]}{A[hi]-A[lo]}$$

正如这个图所画的是一本英文词典中abcd一直到z开头的单词各自起始的页码,它大致是1300多页，换而言之如果它确实是一个大致平均分布的话，每一个字母大概占50页，所以我们可以大致估算出来从1到50页大概是a，50页到100页大概是b，100页到150页大概是c，诸如此类。比如说去查binary (b)，那么因为它是第二个字母所以它大概会在整书从2/26这个位置开始，而search,s是第19个元素 所以大概它会位于19/26的位置。正因为这种算法在确定切分点也就是轴点的时候，采用的是近似的插值估算的方法，所以我们也称之为Interpolation Search插值查找，下面是一个实例。

性能

从刚才的例子我们可以看出，对于这样一个长度为19的有序向量，只用了3次比较就给出了答案，而在通常的二分查找中这是做不到的，所以我们已经看到它在某些情况下确实很快，但是它总是能很快吗？包括这种很快到底定性是多大呢？

我们需要做一个严格的界定，首先一个不好的消息是插值查找在某些情况下效率会很低，比如说 可能退化为与平凡的顺序查找没有什么区别，我们此前所做的那种假设也就是均匀独立的分布不满足，或者至少在某些部分不满足以致在全局或某些局部出现一些所谓的病态分布。

• 最坏情况：$O(hi- lo)=O(n)$

当然 插值查找的最好情况也是不言而喻的，和其他的查找差不多，也就是说有可能我们在某次，甚至在第一次猜测的时候就直接命中，那么这种我们也不再考虑。我们转而再考虑一般的情况，也就是平均而言会怎么样。

这里我们需要用到一个非常基础类似引理的结论这个结论：在插值查找算法中每经过一次迭代，或者说每经过一次比较，都可以将查找的范围也就是减而治之之后剩余的部分由原先的规模n缩减为$\sqrt{n}$。

• 平均情况：每经过一次比较，$n$缩减至$\sqrt{n}$。
• 于是，待查找区间宽度将按一下趋势缩减：

​ $n,\quad\sqrt{n},\quad \sqrt{\sqrt{n}},\quad \sqrt{\sqrt{\sqrt{n}}},\dots,\quad2$

​ $n,\quad n^{(1/2)},\quad n^{(1/2)^2},\dots,\quad n^{(1/2)^k},\dots,\quad2$

• 经多少次比较之后，有$n^{(1/2)^k}<2$？

  $k>loglogn$

• 插值查找的时间复杂度为：$O(loglogn)$

我们同样可以来估算：如果向量的长度或者这个区间的宽度是n的话，考虑这个n按照二进制打印出来以后的位宽就是以的2为底 logn，那么每一次将它变为根号n从二进制的打印宽度来看其实就是变成了1/2的原来那么多宽度，换而言之每一次开方其实同步的是使宽度变成了原来的1/2，这样的过程 从n的数位宽度来说是一个不断折半的过程。

回顾此前的二分查找，如果是对的n的数值每次折半的话，那么这里的插值查找实际上就是对n的二进制位宽度来做二分查找。二分查找所需要的迭代次数是与它的初始值呈一个对数关系的，即$O(logn)$，而插值查找的位宽的初值相当于是logn，所以其需要的迭代次数就是$O(loglogn)$。

从今以后也许我们应该学会忘掉这些复杂的，虽然是精确的数学，而改用这种宏观的大趋势的把握本质的习惯。

综合对比

现在将插值查找和其他的算法综合起来进行比对和考量，刚才插值查找所实现的这种改进也就是从logn到loglogn
虽然从数学上是一个比较大的改进，但从实际效率来看却值得商榷。

• 从$O(logn)$到$O(loglogn)$，是否值得？

• 通常优势不明显，除非查找区间宽度极大，或者比较操作成本极高。

  比如，n = 2^(2 ^ 5) = 2 ^ 32 = 4G时，$log_2(n)=32,\quad log_2(log_2(n))=5$

• 易受小扰动的干扰和“蒙骗”，可能在局部花费非常多的时间

• 须引入乘法、除法运算，相对而言成本更高（二分查找只需加法，Fibonacci查找只需加法和减法）

所以可行的查找算法也许应该将插值查找以及此前的那些查找算法各自的优势综合结合起来，比如说插值查找更善于在比较大的一个宏观的范围内，将问题的关注点尽可能快的缩小到一定的范围，即它比较擅长于处理那种极大的情况，然后一旦到了比较小的情况，这种容易受到干扰包括蒙骗尤其是乘法除法这样的一些overhead额外计算占得比重就会更大成为不可忽略的因素，而在这个时候二分查找的优势就体现出来了。

• 实际可行的方法：

  首先通过插值查找，将插值范围缩小到一定的范围，然后再进行二分查找，或者顺序查找，即：

  • 大规模：插值查找
  • 中规模：折半查找
  • 小规模：顺序查找