学算法一定要了解斐波那契算法，它也是顺序查找算法的一种，可以非常精准定位要查找的数据，又称为“黄金分割”查找算法。
斐波那契数列
斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、····，在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。
斐波那契数和数据有什么关系？
斐波那契数列中(上表来自维基百科)，从第三项开始，每一项都等于前两项之和：
上述性质可以用于数据区间分割，将一个长度为F(n)数组看做前后两半，前面一半长度是F(n-1)，后面一半的长度是F(n-2)。正是这个想法将斐波那契数列和数组联系到一起，也是后面分析的基础。
斐波那契查找同样是查找算法家族中的一员，它要求数据是有序的（升序或降序）。斐波那契查找采用和二分查找/插值查找相似的区间分割策略，都是通过不断的分割区间缩小搜索的范围。
其中n的取值是任意长度的，即对任意长度的数组都能找到对应的斐波那契数，下面将具体介绍斐波那契查找的步骤。
原理分析
斐波那契查找的整个过程可以分为：
- 构建斐波那契数列；
- 计算数组长度对应的斐波那契数列元素个数；
- 对数组进行填充；
- 循环进行区间分割，查找中间值；
- 判断中间值和目标值的关系，确定更新策略；
- 构建斐波那契数列如下：
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
- 计算数组长度对应的斐波那契数列元素个数
假设手中的数据如下：
[1, 2, 4, 6, 7, 9, 13,
16, 17, 21, 23, 25, 27,
31, 45, 56, 58, 61, 65,
67, 73, 75, 88, 93, 102]
可知上述数据共25个元素，不对应1.1节中的斐波那契数列中任何F(n)，这种情况是很常见的。此时，策略是采用“大于数组长度的最近一个斐波那契数值”。比如当前数组长度为25，斐波那契数列中大于25的最近元素为34。
- 对数组进行填充
确定了斐波那契数值后，就要进行数值填充，即将数组从25个元素填充到34个。填充时，将第26到34个元素均采用第25个元素值进行填充，即最大值填充。 - 循环进行区间分割，查找中间值
这一个步骤与前面介绍的二分查找和插值查找相似，都是不断的缩小搜索区间，进而确定目标值的位置。区间分割公式如“要点”所述，每次分割中间位置的计算如下：
image.png
此时数组被分割为左右两个区间，左边区间含有F(n-1)个元素，-1是因为下标从0开始（比如F(1)表示两个元素）。 - 判断中间值和目标值的关系，确定更新策略
中间值和目标值有三种大小关系，分别对应三种处理方式：
- 相等，则查找成功，返回中间位置即可；
- 中间值小于目标值，则说明目标值位于中间值到右边界之间（即右区间），右区间含有F(n-2)个元素，所以n应该更新为n=n-2；
- 中间值大于目标值，这说明目标值位于左边界和中间值之间（即左区间），左区间含有F(n-1)个元素，所以n应更新为n=n-1；
可能有人要问mid = low + F[k-1] - 1怎么来的？
接下来我们图解一下：
举例：
对于斐波那契数列：1、1、2、3、5、8、13、21、34、55、89……（也可以从0开始），前后两个数字的比值随着数列的增加，越来越接近黄金比值0.618。比如这里的89，把它想象成整个有序表的元素个数，而89是由前面的两个斐波那契数34和55相加之后的和，也就是说把元素个数为89的有序表分成由前55个数据元素组成的前半段和由后34个数据元素组成的后半段，那么前半段元素个数和整个有序表长度的比值就接近黄金比值0.618，假如要查找的元素在前半段，那么继续按照斐波那契数列来看，55 = 34 + 21，所以继续把前半段分成前34个数据元素的前半段和后21个元素的后半段，继续查找，如此反复，直到查找成功或失败，这样就把斐波那契数列应用到查找算法中了。
查找算法
对于一个数组来说，如果数组长度为斐波那契数列中的某一个数字，那么我们就可以用黄金分割比例来分割该数组。当然，如果数组长度没有达到要求，那么我们可以尝试它扩大来满足要求，所以这就是算法的要求。
其实，该算法的本质也还是二分法，只不过跟插入排序法一样，也是将目标的mid值改变成其它的，以至于分割的结果不一样，查找的效果也不一样。
那么具体是怎样分割的呢？
这里用图片直观理解一下：
也就是说，真正需要我们做的是找到这个mid，这里给出公式：mid = F(k-1)-1，你也可以从图片中看出来，数组下标是从：0~F[k]-1，将原来的分成两半，再比较来查找。
斐波那契查找原理与前两种相似，仅仅 改变了中间结点（mid）的位置，mid不 再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1 （F代表斐波那契数列）
对F(k-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
- 类似的，每一子段也可以用相同的方式分割
- 但顺序表长度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));
}
}
