本文系转载文章，阅读原文可读性会更好些，原文链接：
https://mp.weixin.qq.com/s/Xxuwk6DfcP_v46JwoYOUcw

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=5
while (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);
}
}