什么是斐波那契搜索介绍
斐波那契搜索(Fibonacci search) ，又称斐波那契查找，是区间中单峰函数的搜索技术。
斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F，将原查找表扩展为长度为F(如果要补充元素，则补充重复最后一个元素，直到满足F个元素)，完成后进行斐波那契分割，即F个元素分割为前半部分F个元素，后半部分F个元素，找出要查找的元素在那一部分并递归，直到找到。
斐波那契搜索引言
在介绍斐波那契查找算法之前，先介绍一下很它紧密相连的一个概念——黄金分割。黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。斐波那契数列：
1、, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。
相对于折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，比较结果分三种情况：
（1）key值与第mid=（low+high）/2相等，mid位置的元素即为所求；
（2）key值大于第mid=（low+high）/2，则令 low=mid+1；
（3）key值小于第mid=（low+high）/2，则令high=mid-1。
斐波那契搜索也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。
斐波那契搜索简介
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1；开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1)，比较结果也分为三种：
（1）相等，则mid位置的元素即为所求；
（2）>，则low=mid+1，k-=2；
说明：low=mid+1说明待查找的元素在范围内，k-=2 说明范围内的元素个数为n-(F(k-1))=Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。
（3））<，则high=mid-1，k-=1。
说明：low=mid+1说明待查找的元素在范围内，k-=1 说明范围内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找。
在最坏情况下，斐波那契查找的时间复杂度还是O(log2n)，且其期望复杂度也为O(log2n)，但是与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定。
斐波那契搜索斐波那契搜索原理
斐波那契搜索是一种有限区间中单峰函数的搜索技术。为简单起见，设此区间为L1=，记{Fi}为斐波那契数，
第一次估值点为：
和
其中，1/Fn应等于或小于搜索的预期精度。若f(x1)>f(x2)，则删去(x2，1]，反之删去=0; F=1; for(int i=2;iF-1)//计算n位于斐波那契数列的位置 ++k; int * temp;//将数组a扩展到F-1的长度 temp=new int -1]; memcpy(temp,a,n*sizeof(int)); for(int i=n;i<F-1;++i) temp=a; while(low<=high) { int mid=low+F-1; if(keytemp) { low=mid+1; k-=2; } else { if(mid=n则说明是扩展的数值,返回n-1 } } delete temp; return -1; } int _tmain(int argc, _TCHAR* argv) { int a = {0,16,24,35,47,59,62,73,88,99}; int key=100; int index=Fibonacci_Search(a,sizeof(a)/sizeof(int),key); cout<<key<<\" is located at:\"<<index; system(\"PAUSE\"); return 0; }