算法：BinarySearch和FibSearch

wanglinzhizhi Jan 21, 2017

算法：BinarySearch 和 FibSearch

binarySearch(int[] A,int e,int lo,int hi){
  while(lo<hi){
  	int mid=(lo+hi)/2;
    if(e<A[mid])
      hi=mid;
    else if(A[mid]<e)
      lo=mid+1;
    else
      return mid;
  }//while end
  return -1;
}//code end

以上是简单的二分查找，对于有序数列，我们常用的是二分查找对其进行遍历，查找到相应所需要的元素的位置。当元素不存在时，返回-1.

算法的时间复杂度是我们愿意欣然接受的O(logn).

这就是最好的了吗？不是，还有比二分查找更好的算法FibSearch。

int fibSearch(int[] A,int e,int lo,int hi){
  Fib fib(hi-lo);
  while(lo<hi){
    int mid=lo+fib.get()-1;
    if(e<A[mid]) hi=mid;
    else if(A[mid]<e) lo=mid-1;
    else return mid;
  }//while end
  return -1;
}//code end
//Fibonacci 类
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)时间
};

以上是fibSearch的基本代码。

事实上，从代码可以看出，fibSearch的算法是基于二分查找的结构之上的。区别在于，每次对mid定位不再是取中点，而是取黄静分割点。这样做对性能的影响是，原来的二分查找BinarySearch的平均复杂段是 1.5*logn，可减低前面的常系数 1.5 降到黄金分割率 (约为1.44）.

之所以会是这样，是因为 binarySearch 中左右两边分支时，进行的比较次数时不同的，左边比较次数比右边的比较次数少，那么虽然每次是平均从中间截断，但是效果并不是分摊，而是后面分摊的比较次数更多。所以可以用fibSearch将比较次数更少的左边截取更长的长度，这有点类似于哈夫曼编码的方式，将较小权值的分支分更深，而将将较大权值的分支放在更浅的位置已达到整体的权值最小。

另外一个发现是关于fibonacci数列的。以前只知道有 Fibonacci数列，但是没有想过它的用途，现在发现这货还是很有用的。而且原来Fibonacci 数列与黄金分割点之间存在相关关系。

tips，fibonacci数列千万不要使用递归来构造。 :)

###update 2016.02.27

之前一直很忙（懒）导致之前貌似有个与二分查找有极大相关性的一个话题的个人领悟想写一写的，然而，现在忘了。。。

好吧，还是先记录下我现在想些的内容吧：

对于比较次数的锱铢必较。其实上面的BinSearch算法如果不仔细考虑比较次数的问题，其实性能提升就无从谈起，我记得以前在复习《数据结构》这门课程的时候，做算法题很不理解为什么经常会有比较不同算法之间的比较次数的多少，觉得很无聊。（总觉得比较不同算法之间交换元素的次数的不同很容易理解，因为毕竟交换元素有的时候开销是明明白白摆在那里的，但是就比较次数有什么好计较的？？？），现在才知道当年还是太年轻。

我在闲着无聊的时候重新看了一下数据结构的内容，如果针对比较次数的限制，我们对BinSearch算法是可以进一步优化的，即使在向右跳转的时候和向左跳转方向都只需要相同的比较次数的思路。

怎么做呢？具体说来，其实只需要做及其微小的变化就可以了。mid=(low+high)/2;只是现在不需要进行A[mid]进行三次比较(大于，小于，等于)。而是将只考虑两种情况：a：e < A[mid], b：A[mid]<=e;

>
>    ( e < A[mid] ) ? high = mid : low = mid;
>
>

这样处理之后，算法中分支向左或向右都只需要1次比较。那么就出现了新的问题，这样做算法什么时候终止呢？是的，终止条件发生了变化，不再是当遍历到我们需要的e==A[mid]的时候返回，而是在折半到最后low<high 才终止。也就是说，当e与A[mid]比较之后，将向量分为两部分[lo, mi)或[mi, hi),每一次比较从这两部分中选择一边深入下去，相同的故事一直进行直到最后不满足low<high 循环条件才退出。

DSA如下：

>
>     binSearchAgl2(int[] A,int e,int low,int high){
>       while(low<high){
>         ( e < A[mid] ) ? high = mid : low = mid;
>       }//while end
>       if(e ==A[mid])
>         return mid;
>       else
>         return -1;
>     }//code end
>

这样做是否值得呢？优点不难看出，随着比较次数的减少，整体效率会有所上升，但是缺点也很明显，最好情况和最坏情况一样，都是等于平均情况下的效率。

对于上述三种排序思路，如何选择最优呢？和小时候做数学题一样，分情况讨论，二分排序问题，是输入敏感型的，对输入的向量（为简单，假设为向量）很敏感。

对于输入的向量，如果出现最好和最坏现象比较频繁，数据分布有明显的聚集现象，那么很显然，binSearch不是最好的选择，应该选择更看重平均效率的算法。

反之，对于有序数据向量来说，数据在向量中分布均匀，那么经典的binSearch将会是适合的。

好吧，终于到第二了，这次说什么都要先把主要的观点记下来，免得又忘了。

第二，是关于在数据结构中二分搜索的地位的评价的。

这几天闲着无聊，感觉什么都不做太浪费宝贵的人生了，于是我就把数据结构重新遍历了一边，个人观点，二分查找，基本上串连了整个数据结构的内容。类似一根穿针线，在整个数据结构中，时隐时现，重最初的向量的二分查找，到后面树的查找，再到BST(二叉平衡树)的查找算法，再到B-Tree，虽然拓扑结构和逻辑结构上有些不同，但是吧，说实话其实思路倒还真是——起码我觉得——差不多。具体的思路缕析慢慢来，先补另外几篇……

参考资料：《数据结构》邓俊辉清华大学出版社

by wanglinzhizhi