斐波那契查找(黄金分割法)超详细详解

斐波那契查找思路

说句实在话，这个斐波那契查找我看了不下5遍才理解他的思路和代码，因为它里面的值太多，不好理解容易绕晕，所以我给大家用自己的理解讲一下

什么是斐波那契

要想学会斐波那契查找，首先你得知道什么是斐波那契数列

斐波那契数列，又称黄金分割数列，指的是这样一个数列：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]，将原查找表扩展为长度为Fn，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。

值得一提的是当有序表的元素个数不是斐波那契数列中的某个数字时，需要把有序表的元素个数长度补齐，让它成为斐波那契数列中的一个数值，补上的数值是原数组的最后一个元素，当然把原有序表截断肯定是不可能的，不然还怎么查找。然后图中标识每次取斐波那契数列中的某个值时(F[k])，都会进行-1操作，这是因为有序表数组位序从0开始的，纯粹是为了迎合位序从0开始

如果这样你还是不明白，我只能举例给你来说明

比如有一个数组arr={1，2，3，4，5，6，7，8，9，10，11，12}要对他进行斐波那契查找，查找的值是10

首先，你得创建一个斐波那契数列出来我们定义为f[k],长度暂且定义为10吧那f={1,1,2,3,5,8,13,21,34,55},创建好了之后，我们再看原数组长度arr.length=12，根据斐波那契查找原则我们发现他的长度不等于斐波那契数列的某一个数值，所以我们要将数组的长度补至最近的斐波那契数，好，我们最近的值是13，所以我们复制最后一个元素至arr数组末尾(当然，数组长度是不能改变的，我们只能创建一个新的数组来复制arr数组的值并复制最后一个元素添加到末尾)，好，新的数组元素就是{1，2，3，4，5，6，7，8，9，10，11，12，12}

接下来得找查找算法里的中间值了，斐波那契查找发就是讲原序列分为斐波那契数组里的连续的两个值，上面我们说了原序列长度为13，在斐波那契数列里找到f[k]=f[k-1]+f[k-2],即13=8+5,f[6]=f[5]+f[4],则中间值就是f[5]=8

找到中间值之后下来就是递归了，将目标值和中间值进行比较，如果目标值小于中间值，说明向左递归，将左边的部分继续分解为两个斐波那契数，以此类推直到找到目标数

代码 package search;import java.util.Arrays;public class FibonacciSearch {public static int maxSize = 20;public static void main(String[] args) {int [] arr = {1,8, 10, 89, 1000, 1234};System.out.println("index=" + fibSearch(arr, 189));// 0}//因为后面我们mid=low+F(k-1)-1，需要使用到斐波那契数列，因此我们需要先获取到一个斐波那契数列//非递归方法得到一个斐波那契数列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;}//编写斐波那契查找算法//使用非递归的方式编写算法/** * * @param a 数组 * @param key 我们需要查找的关键码(值) * @return 返回对应的下标，如果没有-1 */public static int fibSearch(int[] a, int key) {int low = 0;int high = a.length - 1;int k = 0; //表示斐波那契分割数值的下标int mid = 0; //存放mid值int f[] = fib(); //获取到斐波那契数列//获取到斐波那契分割数值的下标while(high > f[k] - 1) {k++;}//因为 f[k] 值 可能大于 a 的 长度，因此我们需要使用Arrays类，构造一个新的数组，并指向temp[]//不足的部分会使用0填充int[] temp = Arrays.copyOf(a, f[k]);//实际上需求使用a数组最后的数填充 temp//举例://temp = {1,8, 10, 89, 1000, 1234, 0, 0} => {1,8, 10, 89, 1000, 1234, 1234, 1234,}for(int i = high + 1; i < temp.length; i++) {temp[i] = a[high];}// 使用while来循环处理，找到我们的数 keywhile (low temp[mid]) { // 我们应该继续向数组的后面查找(右边)low = mid + 1;//为什么是k -=2//说明//1. 全部元素 = 前面的元素 + 后边元素//2. f[k] = f[k-1] + f[k-2]//3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]//4. 即在f[k-2] 的前面进行查找 k -=2//5. 即下次循环 mid = f[k - 1 - 2] - 1k -= 2;} else { //找到//需要确定，返回的是哪个下标if(mid