两个查找算法都是针对有序数组进行查找，不同点在于分界点的取值不同。
算法介绍
折半查找很简单，每次与当前区间的中点进行比较，然后决定查找前一部分还是后一部分。
Fibonacci查找利用了Fibonacci序列每一项等于前两项和的特点进行划分，然后再在前一部分或者后一部分进行查找。
对于一个数组，我们首先将他填充成长度为F[k]-1的数组，其中F[]表示斐波那契数列。为什么非要填充成F[k]-1呢？
我们知道斐波那契数列有如下性质：
F[k]=F[k−1]+F[k−2]F[k]=F[k-1]+F[k-2] F[k]=F[k−1]+F[k−2]
朴素的想法是我们对区间[l,r)进行划分，其中r-l=F[k]，分界点选择为mid=l+F[k-1](当然我们也可以选择F[k-2]，这取决于数据集中在哪里)。当我们将需要查询的数据x和a[mid]比较以后我们可能需要查询左边或者右边的区间，即[l,mid)或者[mid+1,r)，而这个时候后面那个区间的长度为F[k-2]-1，不再是斐波那契数列。这显然不是我们想要看到的结果。
我们不妨尝试将区间的长度变成F[k]-1，将分界点设置为mid=l+F[k-1]-1,这时我们发现右边的区间的长度将变成F[k-2]-1，仍旧满足这种结构。这样我们就可以递归地进行处理。
我们也可以尝试将区间长度变为F[k]+1，只是这样的话我们就无法将区间长度变为0退出搜索。
实现代码
#include<cstdio>#include<algorithm>#include<cstdlib>using namespace std;int init(int* F,int n){F[0]=1;F[1]=1;int ret=2;while(1){F[ret]=F[ret-1]+F[ret-2];if(F[ret]-1>=n)break;++ret;}return ret;}int FiboSearch(int *a,int *F,int k,int l,int r,int x){if(r<l) return -1;int mid=l+F[k-1]-1;if(x==a[mid]) return mid;if(x<a[mid]){return FiboSearch(a,F,k-1,l,mid,x);}else{return FiboSearch(a,F,k-2,mid+1,r,x);}}int main(){int n,k;printf("n="); scanf("%d",&n);printf("k="); scanf("%d",&k);int F[64],len;int a[128];len=init(F,n);for(int i=0;i<n;++i){scanf("%d",&a[i]);}if(k>a[n-1] || k<a[0]){printf("-1\n");return 0;}printf("%d\n",FiboSearch(a,F,len,0,F[len]-1,k));return 0;}
性能分析
斐波那契查找算法同折半查找一样复杂度都是O(logn)的，不同点在于，当数据是均匀分布的时候折半查找更加优秀，当数据是指数分布的时候斐波那契查找算法更好。
