基本介绍斐波那契指的是将一条线段分成两部分，使得一部分与全长的比值等于另一部分与全长的比值。这部分。它的前三位数字的近似值是0.618。因为按照这个比例设计出来的造型非常漂亮，所以又被称为黄金分割，又称中外比例。斐波那契数列{1,1,2,3,5,8,13,21,34,55}求斐波那契数列中相邻两个数的比值，无限接近黄金分割值0.618。斐波那契Naci搜索原理斐波那契搜索原理类似于二分搜索和插值搜索，只是改变了中点（mid）的位置，mid不再是从中点或插值得到，而是位于黄金分割点附近，即即，mid=low+F(k-1)-1，F代表斐波那契数列，对F(k-1)-1的理解如下图所示：由于斐波那契数列F[k]=F[k-1]+F[k-2]的性质，可以得到**(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1**。公式说明：主序表的长度为F[k]-1，那么主序表可以分为两段，长度分别为**F[k-1]和F[k-2]**，即如上图所示。因此中间位置是：mid=low+F(k-1)-1。同样，每个字段都可以用类似的方式拆分。但是序列表的长度n不一定正好等于F[k]-1，所以需要将原序列表的长度n增加到F[k]-1。只要这里的k值可以让F[k]-1刚好大于等于n，就可以通过下面的代码得到。序列表长度增加后，新加入的位置（从n+1到F[k]-1）全部赋给位置n的值。while(n>fib(k)-1){k++;}codecasepackagecom.xie.search;publicclassFibonacci{publicstaticvoidmain(String[]args){intarr[]={1,8,10,89,1000,1234};intn=6;intx=1;//int[]arr=newint[100];//for(inti=0;i<100;i++){//arr[i]=i;///intn=100;//intx=1;System.out.println("Foundatindex:"+fibMonaccianSearch(arr,x,n));}/***返回x和y的最小值**@paramx*@paramy*@return*/publicstaticintmin(intx,inty){return(x<=y)?x:y;}/***Fibonacci搜索x的索引，如果找到索引位置则返回，否则返回-1*
*算法说明：*令arr[0..n-1]为输入数组，要查找的元素为x。*1.找到大于或等于n的最小斐波那契数。将此数设为fibM[第m个斐波那契数]，*将前面两个斐波那契数设为fibMm1[第(m-1)个斐波那契数]和fibMm2[第((th)个斐波那契数]m-2)斐波那契数].*2.当数组中有要检查的元素时：*a。比较x与fibMm2覆盖范围的最后一个元素，如果x匹配，则返回索引；*乙。如果x小于该元素，则将三个Fibonacci变量向前移动两个Fibonacci，表示大约消除了剩余数组的最后三分之二；*C。如果x大于该元素，则三个斐波那契变量向后移动一个斐波那契。将偏移量重置为索引。这些加在一起表明阵列其余部分的大约三分之一被消除了；*3.由于可能还有一个元素要比较，请检查fibMm1是否为1。如果是，则将x与该剩余元素进行比较。如果匹配，则返回索引。**@paramarrarray*@paramxlookupvalue*@paramnarraylength*@returnxindexpositionor-1*/publicstaticintfibMonaccianSearch(intarr[],intx,intn){//初始化斐波那契数//th(m-2)FibonaccinumberintfibMMm2=0;//第(m-1)个FibonaccinumberintfibMMm1=1;//第m个FibonaccinumberintfibM=fibMMm2+fibMMm1;/*fibM会存储大于等于n的最小Fibonacci数*/while(fibM