斐波那契查找算法

 斐波那契查找原理，仅仅改变了中间结点(mid)的位置，mid不再是中间或插值得到,而是位于黄金分割点附近，即mid=low+F(k-1)-1(F代表斐波那契数列)

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]-1和F[k-2]-1的两段

从而得到中间位置mid = low+F(k-1)-1

package day7_11;import java.util.Arrays;public class Test {public static int maxSize = 20;public static void main(String[] args) {int[] arr =  {1,8,10,89,1000,1234};int i = fibSearch(arr, 1234);System.out.println(i);}public static int[]fib(){int[] f = new int[maxSize];f[0] = 1;f[1] = 1;for(int i=2;i<maxSize;i++){f[i] = f[i-1] + f[i-2];}return f;}//使用非递归的方式/**** @param a 数组* @param key 我们需要查找的关键码(值)* @return  返回对应的下标，如果没有-1*/public static int fibSearch(int[] a,int key){int low = 0;int high = a.length-1;int k =0;int mid = 0;int f[] = fib();while (high > f[k] -1 ){k++;}//因为f[k]值可能大于a的长度，因此我们需要使用Arrays类，构造一个新的数组，并指向a[]//不足的部分会使用0填充int[] temp = Arrays.copyOf(a,f[k]);//实际上需求使用a数组最后的数填充temp//temp = {1,8,10,89,1000,1234,0,0,0} => {1，8，10,89,1000,1234,1234,1234,1234}for(int i=high+1;i<temp.length;i++){temp[i] = a[high];}//使用while来循环处理，找到我们的数keywhile (low<=high){mid = low+f[k-1]-1;if(key<temp[mid]){ //我们应该继续向数组的前面查找high = mid - 1;//为什么是k-1//说明//1.全部元素 = 前面的元素 + 后边的元素//2.f[k] = f[k-1] + f[k-2]//因为前面有f[k-1]个元素，所以可以继续拆分f[k-1] = f[k-2] + f[k-3]//即在f[k-1]的前面继续查找k--//即下次循环mid = f[k-1-1]-1k--;}else if(key>temp[mid]){low = mid + 1;//为什么是k-=2//说明//1.全部元素 = 前面的元素+后边元素//2.f[k] = f[k-1] + f[k-2]//3.因为后面我们有f[k-2]所以可以继续拆分f[k-1] = f[k-3] + f[k-4]//4.即在f[k-2]的前面进行查找k-=2//5.即下次循环mid = f[k-1-2]-1k -=2;}else{ //找到//需要确定，返回的是哪个下标if(mid<=high){return mid;}else{return high;}}}return -1;}}