和插值查找法一样，斐波那契查找（Fibonacci Search）算法也是有序表的一种查找方式，同样属于二分查找的一个优化，它是利用了黄金分割原理（斐波那契数列）来实现的。一般情况下斐波那契查找算法的速度比二分法要快的多，能有效减少查找循环的次数。改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列）。

1、斐波那契查找（Fibonacci Search）算法介绍

用途：能在大量的数据中找到自己想找的元素，减少查找的循环的次数。

条件：斐波那契查找（Fibonacci Search）算法类似于二分查找法和插值查找，必须是有序列表。对于非有序序列，可以先进行排序后再使用插值查找算法查找。

原理：

• 对一个有序数列进行查找的时候，二分法（即折半查找）是利用中间值middle来一步步缩小搜索的范围，直至找到最终结果。时间复杂度：O(log(n))。
• 插值查找算法同二分法类似，唯独中间值middle的计算方式不一样，该middle值会尽可能的接近我们要查找的值，减少查找的次数，时间复杂度一样为 O(log(n))。
• 斐波那契查找（Fibonacci Search）算法和二分法及插值算法一样，不同的是middle值不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列）。

斐波那契数列：

斐波那契数列：即1,1,2,3,5,8,13…，从第三个数开始，后面的数都等于前两个数之和，而斐波那契查找就是利用的斐波那契数列来实现查找的。初始化的斐波那契数列最后一位要大于等于数组元素的size-1。

查找步骤：

假设表中有 n 个元素，查找过程为获取区间的下标 mid=low + fibonacci[k - 1] - 1 ，对 mid 的关键字与给定值的关键字比较：

1. 如果与给定关键字相同，则查找成功，返回mid和high的最小值；
2. 如果给定关键字大，向右查找并减小2个斐波那契区间；
3. 如果给定关键字小，向左查找并减小1个斐波那契区间；
4. 重复过程，直到找到关键字（成功）或区间为空集（失败）。

2、实现方式

2.1 实例1

import org.junit.Test;

import java.util.Arrays;

/**
 * 斐波那契查找算法
 */
public class FibonacciSearch {
    /**
     * 有序的数组
     */
    public int[] elements = new int[]{1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
    /**
     * 对应的斐波拉契数组,数组的最大值>=elements.length-1
     * 本例中elements.length-1==9，所以对应的fibonacci数组的最大值>=9, 取值为13
     */
    public int[] fibonacci = new int[]{1, 1, 2, 3, 5, 8, 13};

    @Test
    public void test() {
        System.out.println(fibonacciSearch(88));
    }

    /**
     * 斐波那契查找的实现
     *
     * @param key 要查找的数据
     * @return 查找到的索引, 或者-1 表示查找到
     */
    public int fibonacciSearch(int key) {
        //最小索引
        int low = 0;
        //最大索引
        int high = elements.length - 1;
        //不在范围内,直接返回-1
        if (elements[low] > key || elements[high] < key) {
            return -1;
        }

        int k = 0, i, mid;
        /*计算high位于斐波那契数列的位置 */
        //这里high为9,fibonacci[5]<9<fibonacci[6] ,取大的,即k=6
        while (high > fibonacci[k]) {
            k++;
        }

        /*扩展数组*/
        //扩展原数组,长度扩展为fibonacci[k]=13,即多加了三个位置elements[10],elements[11],elements[12]
        elements = Arrays.copyOf(elements, fibonacci[k]);
        //为了保证数组的顺序,把扩展的值都设置为原始数组的最大值
        for (i = high + 1; i < elements.length; i++) {
            elements[i] = elements[high];
        }
        /*开始斐波那契查找*/
        while (low <= high) {
            System.out.println("------");
            /* 计算当前分隔的下标索引,取的是黄金分割点 7-4-2-1-0  7-10*/
            mid = low + fibonacci[k - 1] - 1;
            /* 若查找记录小于当前分隔记录 */
            if (key < elements[mid]) {
                /* 最高下标调整到分隔下标mid-1处 */
                high = mid - 1;
                /* 斐波那契数列下标减一位 */
                k = k - 1;
            }
            /* 若查找记录大于当前分隔记录 */
            else if (key > elements[mid]) {
                /* 最低下标调整到分隔下标mid+1处 */
                low = mid + 1;
                /* 斐波那契数列下标减两位 */
                k = k - 2;
            } else {
                /* 若mid <= high则说明mid即为查找到的位置，返回mid */
                /* 若mid>high说明是补全数值，返回high */
                return Math.min(mid, high);
            }
        }
        return -1;
    }
}

2.2 实例2

import java.util.Arrays;

/**
 * 斐波那契查找算法
 */
public class FibonacciSearch {
    public static int Maxsize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 12, 15};
        int val = findVal(arr, 12);
        System.out.println(val);

    }

    //用函数定义一个斐波那契数列
    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;
    }

    public static int findVal(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int f[] = fib();// 调用的斐波那契数列
        int k = 0;//斐波那契数列所以
        int mid = 0;
        while (high > f[k]) {
            k++;
        }
        // 因为斐波那契数组的f[k]值可能大于arr数组的长度，
        // 因此我们要使用Arrays类，构造一个新的数组，并指向arr[], 不足的部分会使用0填充
        int[] temp = Arrays.copyOf(arr, f[k]);
        // 实际上需求用arr最后的值来进行补充
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        // 使用while循环，找到数key, 只要这个条件满足，就可以找
        while (low <= high) {
            System.out.println("---");
            //中间下标
            mid = low + f[k - 1] - 1;
            if (key < temp[mid]) {
                // 要找的数小于中间值，说明在数组的左边 fibIndex--；
                high = mid - 1;
                k--;
            } else if (key > temp[mid]) {
                // 要找的值大于中间值说明在数组的右边
                // fibonacci[fibIndex]=fibonacci[fibIndex-1]+fibonacci[fibIndex-2];
                // fibonacci[fibIndex-1] 为数组左边的值 fibonacci[fibIndex-2]为数组右边的值
                low = mid + 1;
                k -= 2;
            } else {
                // 注意：这里要进行判断返回时是哪个下标
                // 如果mid<=high，返回mid； 如果mid>high，返回high；
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}

3、总结

如上图，斐波那契查找的特点就是左侧半区范围大于右侧半区范围。如果要查找的记录在mid右侧，则左侧的数据都不用再判断了，不断反复进行下去，对处于右侧当中的大部分数据，其工作效率要高一些。 所以尽管斐波那契查找的时间复杂也为O(logn)，但就平均性能来说，斐波那契查找要优于二分查找。可惜如果是最坏情况，比如这里key=1，那么始终都处于左侧长半区在查找，则查找效率要低于二分查找。

还有比较关键的一点，二分查找是进行加法与除法运算（mid=(low＋high)/2），插值查找进行复杂的四则运算（mid=low＋(highlow) * (key-a[low])/(a[high]-a[low])），而斐波那契查找只是最简单加减法运算（mid=low＋F[k-1]-1)，在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率，但是斐波那契额查找同样需要额外的空间。