斐波那契查找算法

学算法一定要了解斐波那契算法，它也是顺序查找算法的一种，可以非常精准定位要查找的数据，又称为“黄金分割”查找算法。

斐波那契数列

在讲算法之前，我们先介绍一下斐波那契数列，该数列公式为F(K) = F(k-1) + F(k-2)，即 1、1、2、3、5、8、13、21……。我们还知道，F(k-1)/f(K)随着K的递增，该数越来越接近黄金分割比例，所以该方法也叫黄金分割法。

查找算法

对于一个数组来说，如果数组长度为斐波那契数列中的某一个数字，那么我们就可以用黄金分割比例来分割该数组。当然，如果数组长度没有达到要求，那么我们可以尝试它扩大来满足要求，所以这就是算法的要求。

其实，该算法的本质也还是二分法，只不过跟插入排序法一样，也是将目标的mid值改变成其它的，以至于分割的结果不一样，查找的效果也不一样。

那么具体是怎样分割的呢？

这里用图片直观理解一下：

image.png
也就是说，真正需要我们做的是找到这个mid，这里给出公式：mid = F(k-1)-1，你也可以从图片中看出来，数组下标是从：0~F[k]-1，将原来的分成两半，再比较来查找。
斐波那契查找原理与前两种相似，仅仅 改变了中间结点（mid）的位置，mid不 再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1 （F代表斐波那契数列）

对F(k-1)-1的理解：

1. 由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到 （F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1
2. 类似的，每一子段也可以用相同的方式分割
3. 但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。

javascript代码：

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

对F(k-1)-1的理解：
1.由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到 （F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1           

2.类似的，每一子段也可以用相同的方式分割
3.但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。

 * 
 */

let arr = [1, 8, 10, 89, 1000, 1234, 1555, 1777, 1888, 1999];


console.log('查找1：', fibSearch(arr, 1));
console.log('查找1999：', fibSearch(arr, 1999));
console.log('查找2999：', fibSearch(arr, 2999));
//因为后面我们mid = mid=low+F(k-1)-1,需要使用到斐波那契数列，
//因此我们需要先获取到一个斐波那契数列

function fib(maxSize) {
    let f = new Array(maxSize);
    f[0] = 1;
    f[1] = 1;
    for (let i = 2; i < maxSize; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f;
}

//编写斐波那契查找算法
/**
 * 
 * @param {数组} arr 
 * @param {我们需要查找的关键码} key 
 * @return 返回对应的下标，没找到返回-1
 */
function fibSearch(arr, key) {
    let low = 0;
    let high = length = arr.length - 1;
    let k = 0;//表示斐波那契分割值得下标
    let mid = 0;//存放mid值
    let f = fib(20);
    //获取斐波那契分割值得下标
    while (high > f[k] - 1) {
        k++;
    };
    //因为f[k]值，可能大于a的长度，因此我们需要构建一个新的数组
    //用arr数组的最后的数组填充arr数组
    arr = [...arr];
    for (let i = high + 1; i < f[k]; i++) {
        arr.push(arr[high]);
    }
    //使用while来循环处理，找到我们的数key
    while (low <= high) {//只要这个条件满足，就可以找
        mid = low + f[k - 1] - 1;
        if (key < arr[mid]) {
            //我们应该继续向数组的前面查找（左边）
            high = mid - 1;
            //1.全部元素 = 前面的元素 + 后面的元素
            //2.f[k] = f[k-1] + f[k-2]
            //因为前面 f[k-1]个元素，所以可以继续拆分f[k-1] = f[k-2]+f[k-3]
            //即下次循环mid = f[k-1-1] -1
            k--;
        } else if (key > arr[mid]) {
            //我们应该继续向数组的后面查找(右边)
            low = mid + 1;
            //1.全部元素 = 前面的元素 + 后面的元素
            //2.f[k] = f[k-1] + f[k-2]
            //3，因为后面我们有f[k-2]，所以可以继续拆分 f[k-2] = f[k-3]+f[k-4]
            //4.即在f[k-2]的前面进行查找 k-=2
            //5.即下次循环mid = f[k-1-2] -1
            k -= 2;
        } else {
            //找到
            //需要确定，返回的是哪个下标,因为可能找到扩充的元素的下标
            if (mid <= length) {
                return mid;
            } else {
                return length;
            }
        }
    }
    return -1
}

java代码:

package com.jd.sign;

import java.util.Arrays;

/**
 * @Author 斐波那契数组
 * 要查找某数组中值，先把数组适配成斐波那契数组的长度，不足则用arr数组的最后的数组填充arr数组
 * 然后使用fib数组特点，f(k) = f(k-1)+f(k-2) 计算出mid值 mid = f(k-1)-1
 * 因mid索引位置的值最接近于要查找的值，再根据大小挨个对比查找。
 * @create 2021/1/16 9:57
 */
public class Fib {
    public static int maxSize = 20;

    public static int[] getFibonacci() {
        int[] fib = new int[maxSize];
        fib[0] = 1;
        fib[1] = 1;
        for (int i = 2; i < maxSize; ++i) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib;
    }
    public static int FibSearch(int[] arr, int value) {
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        int[] fib = getFibonacci();
        int k = 0;
        while (high >= fib[k] - 1) {
            k++;
        }

        //拷贝原数组并把长度调整到fib长度，用arr数组的最后的数组填充arr数组
        int[] tmp = Arrays.copyOf(arr, fib[k]);
        for (int i = arr.length; i < fib[k]; ++i) {
            tmp[i] = arr[high];
        }

        while (low <= high) {
            mid = low + fib[k - 1] - 1;
            if (value < tmp[mid]) {
                high = mid - 1;
                k--;
            } else if (value > tmp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 99, 100 };
        System.out.println("index = " + FibSearch(arr, 99));
    }
}