斐波那契数列查找算法

java实现斐波那契数列查找算法

什么是斐波那契数列？
斐波那契数列指的是这样一个数列： 0, 1, 1, 2, 3, 5, 8, 13, 21....

特别指出： 第0项是0，第1项是第一个1

这个数列从第三项开始，每一项都等于前两项之和。

斐波那契公式： F(k)=F(k-1)+F(k-2) 提示：F(1)=1 F(2)=1

基本原理：

斐波那契查找原理与二分查找算法相似也要求数组有序，与二分查找算法相比仅仅改变了中间结点(mid)的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=left + fibona[k - 1] - 1 (fibona代表斐波那契数列)

java代码实现：

//斐波那契数列 查找算法
public class FibonacciSearch {
    //斐波那契数列的大小
    public static int maxSize = 10;

    public static void main(String[] args) {
        int[] arr = {10, 11, 12, 50, 60, 99, 100};
        int index = fibonacciSearch(arr, 100);
        System.out.println("index=" + index);

    }


    //创建一个斐波那契数列
    public static int[] fid() {
        int[] arr = new int[maxSize];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr;
    }


    /**
     * 利用斐波那契  查找对应的元素
     *
     * @param arr 待查找的数组
     * @param key 待查找的数
     * @return 如果找到就返回对应数的下标，如果找不到就返回-1.
     */
    public static int fibonacciSearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;
        int[] fibona = fid();
        int k = 0;
        //将创建一个适合斐波那契数列的数组
        while (right > fibona[k] - 1) {
            k++;
        }
        int[] temp = Arrays.copyOf(arr, fibona[k]);
        for (int i = right + 1; i < fibona[k]; i++) {
            temp[i] = arr[right];
        }

        int mid = 0;
        while (left <= right) {
            mid = left + fibona[k - 1] - 1;
            if (key < temp[mid]) {
                right = mid - 1;
                k -= 1;
            } else if (key > temp[mid]) {
                left = mid + 1;
                k -= 2;
            } else {
                if (mid < right) {
                    return mid;
                } else {
                    return right;
                }
            }
        }
        return -1;
    }
}