package A;

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
//此方法也同样需要在有序数列中查找
public class JosePhu {
    public static void main(String[] args) {
        Method method = new Method();
        int[] a={1,5,6,6,7,8,9,10,89,89};
        System.out.println(method.fibonacciSearch(a,6));

    }
}

package A;

import java.util.ArrayList;
import java.util.Arrays;

public class Method {
    public int[] fib(){
        int maxsize=20;
        int[] f=new int[maxsize];
        f[0]=f[1]=1;
        /*System.out.println(f[0]);
        System.out.println(f[1]);*/
        for (int i = 2; i < f.length; i++) {
            f[i]=f[i-1]+f[i-2];
            /*System.out.println(f[i]);*/
        }
        return f;
    }//获得一个斐波那契数列

    public int fibonacciSearch(int[] a,int key){
        int left=0;
        int right=a.length-1;
        int f[]=fib();
        int k=0;
        int mid=0;
        while (right>f[k]-1){//去看那个图，就是说要满足那个图才能进行斐波那契查找，你会发现f[k]-1就是最上面那一行
            k++;
        }
        int[] temp=Arrays.copyOf(a,f[k]);//后面返回的mid可能会超出原数组长度，所以扩容
        for (int i = right+1; i < a.length; i++) {
            temp[i]=a[right];
        }

        while (left<=right){
            mid=left+f[k-1]-1;
            if (key<temp[mid]){
                right=mid-1;
                k--;//因为left和right改变了，k--是代表前面的那一段大括号
            }else if (key>temp[mid]){
                left=mid+1;
                k=k-2;//它相当于原先的right，即后面那一段大括号，所以是k-2。（因为k分2段嘛，一段是k-1，一段是k-2，它们加起来才是k）
            }else {
                if (mid<=right)//返回那个小的,这里的小时指最后temp[i]=a[right]赋值的那里的小，并不是说a数组本身重复的小
                    return mid;
                else
                    return right;
            }
        }
        return -1;
    }
}

因为f[k]=f[k-1]+f[k-2];

所以f[k]-1=f[k-1]-1+f[k-1]-1;

斐波那契查找（黄金分割点查找）