package 查找算法; import java.util.Arrays; //斐波那契查找 public class FibonacciSearch { public static void main(String[] args) { int [] arr={1,5,12,21,30,32,55,68,80,89,90,99}; int key=30; int index=fibonacciSearch(arr,key); System.out.println("index="+index); } private static int fibonacciSearch(int[] arr, int key) { int f[]=getFiboacci(); int low=0; int high=arr.length-1; int mid=0; int k=0; while (high>f[k]-1){ k++; } int [] temp= Arrays.copyOf(arr,f[k]); for (int i=high+1;i<temp.length;i++){ temp[i]=arr[high]; } while (low<=high){ mid=low+f[k-1]-1; System.out.println("mid="+mid); if(key<temp[mid]){ high=mid-1; k-=1; }else if (key>temp[mid]){ low=mid+1; k-=2; }else { if(mid<=high){ return mid; }else { return high; } } } return mid; } private static int[] getFiboacci() { int []f=new int[20]; f[0]=1; f[1]=1; for (int i=2;i<f.length;i++){ f[i]=f[i-1]+f[i-2]; } return f; } }
执行结果
mid=7 mid=4 index=4