PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接

ps：本篇文章写斐波那契查找算法和数组、链表、树的存储形式

1、斐波那契查找算法

斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……；在数学上，斐波那契数列以如下被以递推的办法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2），这里有一个黄金分割点的概念：指把一条线段宰割为两局部，使其中一部分与全长之比等于另一部分与这部分之比，取其前三位数字的近似值是0.618；斐波那契数列中，两个相邻数的比例是有限靠近与黄金分割值0.618。

“把一条线段宰割为两局部，使其中一部分与全长之比等于另一部分与这部分之比，取其前三位数字的近似值是0.618” 这句话是什么意思呢？我来拿斐波那契数列外面的3个数（13、21 和 34）来举个例子，假如有一条绳子34米并把这条绳子命名为A，把A分成两段，一段是13米并命名为A1，另一段是21米并命名为A2；这个时候计算A1的长度除以A2的长度，约等于0.619；计算A2的长度除以A的长度，约等于0.617；这个时候A1/A2 是不是差不多等于A2/A，这回该了解蓝色的那一句话的意思了吧。

斐波那契查找算法与二分查找算法很相似，只是在于 mid 的计算不一样；

（1）在二分查找算法中，mid = (0 + array.length) / 2。

（2）在斐波那契查找算法中，咱们要搞明确几个变量，那就是mid、low、high、F(k-1)-1，其中 mid=low+F(k-1)-1，low 示意什么呢？它示意一开始一个数列区间中最右边的下标，比方数组 arr={1,2,3,4,6}，那么 low 一开始就是数组元素1的下标，也就是0；high 示意一开始一个数列区间中最左边的下标，比方数组 arr={1,2,3,4,5,6}，那么 low 一开始就是数组元素6的下标，也就是5；mid 示意[low,high]之间的一个值；由斐波那契数列计算公式 F(k) = F(k-1) + F(k-2) 失去 F(k)-1 = (F(k-1) - 1) + (F(k-2) - 1) + 1，这时候把 F(k)-1 看做一根线总长名叫A，把 F(k-1) - 1 看做是 A 的一部分并命名为 A1，把 1 看做是 A 的一部分并命名为 A2，也就是示意1个数，那便是 mid，把 F(k-2) - 1 看做是 A 的一部分并命名为 A3，所以 mid 即示意[low,high]之间的一个值，也示意 F(k-1)-1 中的一个数。

我画个图来示意

图片

图1

好，咱们举个例子，留神斐波那契数查找算法适宜在有序的数列进行查找，这里有斐波那契数组 f={1,1,2,3,5,8,......}，待查找的数组 arr={1,2,3,4,5,6}，假如咱们从 arr 数组中查找元素6的下标；

算法思路剖析一把：

（1）拿到斐波那契数组 f 。

（2）判断数组 arr 的长度是不是斐波那契数组 f 中的一个元素，显然不是，arr 的长度在斐波那契数组 f 中是大于5而小于8，那么咱们就把数组 arr 复制到一个长度为8的数组 temp 中，复制实现后 temp={1,2,3,4,5,6,0,0}，咱们把 temp 中为0的元素赋值数组 arr 的最大值6，赋值实现后 temp={1,2,3,4,5,6,6,6} 。

（3）判断 low 是否大于 high，如果大于就返回 -1，示意没有找到；low=0，high=arr.length=6，显然不是，程序往下走。

（4）计算 mid ，mid = low + f[k - 1] - 1，数组 temp 的长度是8，8在数组 f 的下标是5，所以k = 5，mid=0 + f[4] - 1=4 。

（5）判断查找值是否小于 temp[mid]，如果成立，那么 high=mid-1，k--，这里为什么是 k--，咱们再把 f[k - 1] - 1 这段（看图1了解）分成 f[(k -1) -1] -1 、mid 和 f[(k -2) -1] -1，所以新的 k 就等于 k-1，也就是 k--；判断查找值是否大于 temp[mid]，如果成立，那么 low = mid + 1，k=k-2，这里为什么是 k=k-2，f[k -2] -1 分成 f[k -3] -1 、mid和 f[k -4] -1 这3局部，也就是 f[(k -2)-1] -1 、mid 和 f[(k -2)-2] -1，所以新的 k 就等于 k-2；判断查找值是否等于 temp[mid]，如果成立，那么再如果 mid <= high，就返回 mid ，如果 mid > high ，就返回 high 。

（6）判断查找值是否大于 temp[4]，显然成立，从新计算 k 和 low，k = 4 - 2 = 2，low = mid + 1 = 4 + 1 = 5 。

（7）从新计算 mid，mid = low + f[k - 1] - 1 = 5 + 1 - 1 = 5 。

（8）判断查找值是否等于 temp[5]，显然成立，又如果 mid <= high，所以返回 mid 。

代码实现一把：

public class Test {

private static int maxSize = 100;
private static int[] fib() {

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

}

public static int fibSearch(int[] arr, int findVal) {

return fibSearch(arr, 0, arr.length - 1, findVal);

}

public static int fibSearch(int[] arr, int low, int high, int findVal) {

if (arr == null || arr.length <= 0)  return -1;int k = 0; // 示意斐波那契数列的下标int[] f = fib(); // 获取斐波那契数组int mid = 0;// 获取斐波那契宰割数值，比方在这个demo中，// 判断数组 arr 的长度是不是斐波那契数组 f 中的一个元素，显然不是，// arr 的长度在斐波那契数组 f 中是大于5而小于8，// 那么咱们就把数组 arr 复制到一个长度为8的数组 temp 中// 8 在斐波那契数组 f 中的下标是5，所以k=5while (high > f[k] - 1) {  k++;}// 如果 f[k] > arr.length ，那么就将 arr 所有元素赋值给数组 temp// 比方在这个demo中，temp={1,2,3,4,5,6,0,0}int[] temp = Arrays.copyOf(arr, f[k]);// 把扩容多进去的数赋予原来arr的最初一个数据// 比方在这个demo中，将temp[6] = arr[5],temp[7] = arr[5]for (int i = high + 1; i < temp.length; i++) {  temp[i] = arr[high];}while (low <= high) {  mid = low + f[k - 1] - 1;  if (findVal < temp[mid]) {    high = mid - 1;    k--;  } else if (findVal > temp[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, 6 };int resultIndex = fibSearch(arr, 6);System.out.println(resultIndex);

}
}