PS：本文为转载文章，原文可读性会更好，文末有原文链接ps：本文写斐波那契搜索算法，数组，链表，树的存储方式1，斐波那契搜索算法斐波那契数列，又称黄金分割数列，指的是这样一个数列：1,1,2,3,5,8，13,21,34,...;在数学上，斐波那契数列递归定义如下：F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2)，这里是黄金分割点的一个概念：指将一条线段分成两部分，使一部分占总长度的比例等于另一部分占这部分的比例，取前三个点该数字的近似值为0.618；在斐波那契数列中，相邻两个数的比值无限接近黄金分割值0.618。“把一条线段分成两部分，使一部分占总长度的比等于另一部分占这部分的比，前三位的近似值为0.618”这句话是什么意思？让我以斐波那契数列中的3个数字（13、21和34）为例。假设有一根34米长的绳子，取名为A，将A分成两段，一段为13米，命名为A1，另一段为21米，命名为A2；此时计算A1的长度除以A2的长度，约等于0.619；计算A2的长度除以A的长度，约等于0.617；这时候，A1/A2是不是几乎等于A2/A呢？这一次，是时候理解蓝色句子的意思了。斐波那契搜索算法与二分搜索算法非常相似，只是mid的计算不同；(1)在二分查找算法中，mid=(0+array.length)/2。(2)在斐波那契搜索算法中，我们需要了解几个变量，即mid,low,high,F(k-1)-1，其中mid=low+F(k-1)-1，low是什么意思是？表示开头的一个数字范围内最左边的下标，比如数组arr={1,2,3,4,6}，那么low就是开头的数组元素1的下标，为0；high表示开始一个数组区间最右边的下标，比如数组arr={1,2,3,4,5,6}，那么low就是开头的数组元素6的下标，也就是5；中意味着[低，高]；F(k)-1=(F(k-1)-1)+(F(k-2)-1)+1，此时将F(k)-1作为A线的总长度，把F(k-1)-1作为A的一部分，命名为A1，把1作为A的一部分，命名为A2，表示1个数，即mid，把F(k-2)-1作为A的一部分，命名为A3，所以mid表示介于[low,high]之间的一个值，也表示F(k-1)-1中的一个数。让我画一张图来代表图1。我们举个例子。请注意，Fibonacci数搜索算法适用于按有序序列进行搜索。这里是斐波那契数组f={1,1,2,3,5,8,...}，要搜索的数组arr={1,2,3,4,5,6}，假设我们搜索arr数组中元素6的下标；算法思维分析1取：(1)得到斐波那契数列f。(2)判断数组arr的长度是否为斐波那契数组f中的元素，显然不是，斐波那契数组f中arr的长度大于5小于8，那么我们将数组arr复制到一个中长度为8的数组temp，复制完成后temp={1,2,3,4,5,6,0,0}，我们将temp中为0的元素赋给数组的最大值6arr,temp={1,2,3,4,5,6,6,6}后赋值完成。(3)判断low是否大于high，大于则返回-1，表示没有找到；low=0，high=arr.length=6，显然不行，程序就下去了。(4)计算mid，mid=low+f[k-1]-1，数组temp的长度为8，数组f中8的下标为5，所以k=5,mid=0+f[4]-1=4。(5)判断搜索值是否小于temp[mid]，如果为真，则high=mid-1,k--，这里为什么是k--，我们把f[k-1]-1section（见图1理解）分为f[(k-1)-1]-1、mid和f[(k-2)-1]-1，所以新的k等于k-1，即是k--;判断search是不是大于temp[mid]的值，如果为真，则low=mid+1,k=k-2，这里为什么是k=k-2,f[k-2]-1分为f[k-3]-1,mid和f[k-4]-1这三部分，即f[(k-2)-1]-1,mid和f[(k-2)-2]-1,所以新的k等于k-2；判断搜索值是否等于temp[mid]，如果为真，则如果mid<=high，返回mid，如果mid>high，返回high。（6）判断lookup值是否大于temp[4]，显然为真，重新计算k和low，k=4-2=2，low=mid+1=4+1=5。（7）重新计算mid，mid=low+f[k-1]-1=5+1-1=5。(8)判断搜索值是否等于temp[5]，显然为真，如果mid<=high，返回中。代码实现：publicclassTest{privatestaticintmaxSize=100;privatestaticint[]fib(){int[]f=newint[maxSize];f[0]=1;f[1]=1;对于(inti=2;i<=maxSize-1;i++){f[i]=f[i-1]+f[i-2];}returnf;}publicstaticintfibSearch(int[]arr,intfindVal){returnfibSearch(arr,0,arr.length-1,findVal);}publicstaticintfibSearch(int[]arr,intlow,inthigh,intfindVal){if(arr==null||arr.length<=0)return-1;intk=0;//表示斐波那契数列的下标int[]f=fib();//获取斐波纳契数组intmid=0;//获取斐波纳契拆分值，比如这个demo中，//判断数组arr的长度是否为斐波纳契数组f中的元素，显然不是，//arr的长度在斐波那契数组f中大于5小于8,//然后我们将数组arr复制到一个长度为8的数组temp//斐波那契数组f中8的下标为5,sok=5while(high>f[k]-1){k++;}//如果f[k]>arr.length，则将arr的所有元素赋给数组temp//例如，在这个demo中，temp={1,2,3,4,5,6,0,0}int[]temp=Arrays.copyOf(arr,f[k]);//将扩展后的数赋值给原arr的最后一个数据//例如，在这个演示中，Settemp[6]=arr[5],temp[7]=arr[5]for(inti=high+1;i
