本文共 2742 字，大约阅读时间需要 9 分钟。

1、算法思想

2、问题描述

3、自推过程

4、代码实现

/**     * @Method getFibonacci     * @Author zhihua.Li     * @Version  1.0     * @Description     * 根据传入最大值的参数获得对应长度的斐波那契数列     * @param maxSize     * @Return int[]     * @Exception     * @Date 2021/2/9 18:19     */    private int[] getFibonacci(int maxSize) {           int[] fibonacci = new int[maxSize];        fibonacci[0] = 1;        fibonacci[1] = 1;        for (int i = 2; i < fibonacci.length; i++) {               fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];        }//        System.out.println(Arrays.toString(fibonacci));        return fibonacci;    }

/**     * @param arr     * @param target     * @Method fibonacciSearch     * @Author zhihua.Li     * @Version 1.0     * @Description 斐波那契查找算法     * 待查找数组必须是有序的     * 借助斐波那契数列，找到黄金分割点，然后通过修改mid值对目标数值进行查找     * @Return int  若找到该元素，返回该元素下标，反之返回-1     * @Exception     * @Date 2021/2/9 10:00     */    private int fibonacciSearch(int[] arr, int target) {           int low = 0;        int high = arr.length - 1;        int k = 0;        //接受斐波那契数列的下标        int mid = 0;        int[] fibonacci = getFibonacci(20);        while (high > fibonacci[k]) {               k++;        //找到斐波那契数列中恰好大于待查找数组长度的元素下标        }        //初始化一个斐波那契长度的数组，并将arr复制到这个数组中        //若arr的长度小于新建数组长度，则用arr的最后一个元素补齐新数组的空缺        //{1,8,10,89,1000,1234} -> {1,8,10,89,1000,1234,1234,1234} -> 6个扩容到8个        int[] temp = Arrays.copyOf(arr, fibonacci[k]);        for (int i = arr.length; i < temp.length; i++) {               temp[i] = arr[arr.length - 1];        }        while (low <= high) {               mid = low + fibonacci[k - 1] - 1;            if (target < temp[mid]) {     //应该向左边查找                //fibonacci[k] = fibonacci[k-1]+fibonacci[k-2]                //前面有f[k-1]个元素，如果向前面查找，那么就对k--，将f[k-1]分割成f[k-2]和f[k-3]                high = mid - 1;                k--;            } else if (target > temp[mid]) {       //应该向右边查找                low = mid + 1;                //fibonacci[k] = fibonacci[k-1]+fibonacci[k-2]                //后面有f[k-2]个元素，如果向后面查找，那么就对k-2，将f[k-2]分割成f[k-3]和f[k-4]                k -= 2;            } else {   //                需要确定返回的是哪个下标//                因为数组是扩容过的，可能会出现最终返回值大于待查找数组的最大下标//                如：{2,3,7,14,22,33,55,75,89,123}，调用方法时参数传入taget=123//                调用方法后返回结果为10，而数组最大下标为9                return mid >= high ? mid : high;            }        }        return -1;  //没找到    }

5、代码测试

@Test    public void test() {           int[] arr = {   2,3,7,14,22,33,55,75,89,123};        System.out.println(fibonacciSearch(arr, 123));    }

运行结果为：10

6、算法分析

本代码实现未使用递归思想，在前面几种查找算法中：折半查找需要进行除法，插值查找需要进行更复杂的乘法和除法，而斐波那契查找只需要使用加法和减法，在数据量较大时优势更明显。

附：其他大佬总结的斐波那契查找算法，配合使用助于理解https://blog.csdn.net/darkrabbit/article/details/90240507