?斐波那契查找原理，僅僅改變了中間結點(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;}}