简介

斐波那契查找算法又称黄金分割查找算法。黄金分割点是把一条线段分成两个部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。

了解斐波那契查找算法就必须了解斐波那契数列，例如这样一组数列{1，1，2，3，5，8，13，21，34，55}。从第三个值开始，其每项的值等于前两项之和，两个相邻数字的比例无限接近与0.618

原理

斐波那契查找原理与二分查找、插值查找相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列），如下图所示：

可以看到，斐波那契查找算法的思路就是把一个斐波那契数列映射到需要查询的数列。通过将斐波那契数列中的每一项的值看成是一个数列中元素的个数，其中，斐波那契数列中的每一项减去1就代表原数列中的下标，因为原数列起始下标是从0开始的。关键是要理解斐波那契是如何对原数列进行划分的。它的划分规则就是借助于一个斐波那契数列。例如有一斐波那契数列{1，1，2，3，5，8，13}，假设长度13是我们需要查询的原数列。根据斐波那契的规则：每项等于前两项之和，比如这里的13 = 8 + 5。然后根据这个规则映射到对原数组划分，则长度13的原数组划分为长度8，和5两个部分。所以对应的下标就是一部分{0到7}（这部分就是F[k - 1],其中的k表示斐波那契数列的下标），另一部分{8到12}(这一部分就是F[k - 2],k同前)。所以根据公式mid = low + F(k - 1) - 1,算出mid = 0 + 8 - 1 等于7,所以原查询数列下标为7是中间值，这也验证了上述的划分结果没有错误，接下来如果没有找到就需要在第一轮划分上接着划分，过程是一样的，都需要借助斐波那契数列。

还有一点需要注意：由于斐波那契数列中的每一项我们看成是一个数列的元素个数，而斐波那契数列中的每一项的值是固定的，但它却不包含所有的值。所以我们需要将原需要查询的数列扩容到大小离斐波那契数列中最接近的那一个数。例如斐波那契数列中有13这么一个项，而我此时的数列长度只有12，所以需要将原数列扩容到13。而扩容部分的值只需要将它设置为原数组的最大值

代码实现

package com.zyp.query;

import java.util.Arrays;

/**
 * 斐波那契查找算法
 * @author zyp
 * @create 2022/2/23
 */
public class FibonacciSearch {
    /**
     * 斐波那契数组的长度
     */
    private static final int MAX_SIZE = 20;

    public static void main(String[] args){
        //待查找数组
        int[] array = new int[]{1,2,3,4,5,6,7,8};
        int index = fibonacciQuery(array, 8);
        System.out.println("找到数据的下标为：" + index);


    }

    /**
     * 获取斐波那契数组
     * @return
     */
    public static int[] getFibonacciArray(){
        int[] fibonacciArray = new int[MAX_SIZE];
        fibonacciArray[0] = 1;
        fibonacciArray[1] = 1;
        for(int i = 2; i < fibonacciArray.length; i++){
            //斐波那契
            fibonacciArray[i] = fibonacciArray[i-1] + fibonacciArray[i-2];
        }
        return fibonacciArray;
    }


    /**
     * 斐波那契查找
     * @param array 有序数组
     * @param data 要查询的数
     * @return 找到的下标，-1表示没有找到
     */
    public static int fibonacciQuery(int[] array,int data){
        int left = 0;
        int right = array.length-1;
        //斐波那契数组的下标
        int k = 0;
        //获取斐波那契数组
        int[] fibonacciArray = getFibonacciArray();
        //知道斐波那契数组下标所对应的值大于或者等于原数组为止
        while(right > fibonacciArray[k] -1){
            k++;
        }
        //将原数组进行扩容,并将扩容的值设置为原数组的最大值
        int[] temp = Arrays.copyOf(array, fibonacciArray[k]);
        for(int i = array.length;i<fibonacciArray[k] -1;i++){
            temp[i] = array[array.length-1];
        }
        //开始查找
        while(left <= right){
            int mid = left + fibonacciArray[k-1] -1;
            //说明查找的值在数组的右边
            if(data > temp[mid]){
                left = mid + 1;
                /**
                 * 这里为什么是k=k-2呢？
                 * 因为fibonacciArray[k] = fibonacciArray[k-1] + fibonacciArray[k-2]
                 * fibonacciArray[k-2]：表示右边
                 * fibonacciArray[k-2] = fibonacciArray[k-3] + fibonacciArray[k-4]
                 * mid = fibonacciArray[k-3] + left -1;
                 * 和原来的 int mid = left + fibonacciArray[k-1] -1; 比较得到k = k-2
                 */
                k = k-2;
            }else if(data < temp[mid]){
                //说明查找的值在数组的右边
                right = mid-1;
                /**
                 * 这里为什么是k=k-1呢？
                 * 因为fibonacciArray[k] = fibonacciArray[k-1] + fibonacciArray[k-2]
                 * fibonacciArray[k-1]：表示左边
                 * 将左边再次进行黄金分割
                 * fibonacciArray[k-1] = fibonacciArray[k-2] + fibonacciArray[k-3]
                 * mid = fibonacciArray[k-2] + left -1;
                 * 和原来的 int mid = left + fibonacciArray[k-1] -1; 比较得到k = k-1
                 */
                k = k-1;
            }else{
                //表示已经找到了
                if(mid >= right){
                    return right;
                }else{
                    return mid;
                }
            }
        }
        return -1;

    }




}