共计 3050 个字符，预计需要花费 8 分钟才能阅读完成。
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 =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);}
}
