原 "二分查找(Binary Search
首先，我们来看一个笔者的拙作，一段二分查找代码
//返回值是key的下标，如果A中不存在key则返回-1
template <class T>
int BinSearch(T* A, const T &key, int lo, int hi)
{
int mid;
while(lo<hi)
{
mid = lo + (hi-lo)/2;
if(key < A[mid])
hi = mid-1;
else if(key > A[mid])
lo = mid+1;
else
return mid;
if(lo==hi && A[lo]==key)
return lo;
}
return -1;
}可以证明，算法的时间复杂度为O(nlogn)，考虑前面的系数的话，大致是O(1.5nlogn)。
但是，这一实现仍有改进的余地。注意到循环只需要1次判断来决定是否转进到左侧，但需要2次判断来决定是否转进到右侧。也就是进入左、右分支前的关键码比较次数不等。
而斐波那契查找正是优化了这点。利用斐波那契数来对传入的数组进行黄金分割，这样前半部分较多而后半部分较少。另外，进入前半部分继续搜索所需的判断只有一次，而进入后半部分继续搜索所需的判断却有两次。如此而来，我们人为造成的这种不平衡，反倒是助长了搜索成本的平衡。
template <class T>
int FibSearch(T* A, const T &key, int lo, int hi)
{
int mid;
Fib fib(hi-lo); //构造一个斐波那契数的类
while(lo<hi)
{
int len = hi-lo;
while(fib.get()>len)
fib.prev(); //如果当前的fib.get()返回值大于len，则取前一个斐波那契数
mid = lo + fib.get() - 1; //分割节点的下标
if(key < A[mid])
hi = mid-1;
else if(key > A[mid])
lo = mid+1;
else
return mid;
if(lo==hi && A[lo]==key)
return lo;
}
return -1;
}这里我们需要构造一个斐波那契数的类。要写好这个类，其实只需要一个数组，用动态规划的算法很好写，这里不再赘述。
既然算法实现好了，我们就对这两种算法的正确性做个小测试吧：
int main()
{
a=0,b=0;
for(int i=0; i<=NUM; ++i)
{
A[i] = i;
}
for(int i=0; i<=NUM; ++i) //正确性验证
{
if( BinSearch(A,i,0,NUM) != FibSearch(A,i,0,NUM) )
{
cout<<"What a fucking day !" <<i<<endl;
}
}
return 0;
}算法性能对比(by fovwin)：
参考资料：1.清华大学MOOC 《数据结构与算法》 by 邓俊辉，第二章
2.Wikipedia - Fibonacci Search Technique (https://en.wikipedia.org/wiki/Fibonacci_search_technique)
3.《"斐波那契查找"真的比二分查找快么？》 by forwin (强烈推荐，C语言实现，代码注释非常清晰 - http://blog.csdn.net/fovwin/article/details/9077017)
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
