斐波那契数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*)。

黄金分割是指将整体一分为二,较大部分与整体部分的比值等于较小部分与较大部分的比值,其比值约为0.618。这个比例被公认为是最能引起美感的比例,因此被称为黄金分割。

斐波那契数列的两个相邻数的比例,无限接近黄金分割值0.618。

斐波那契查找

斐波那契查找算法类似于二分查找,也需要记录是有序的,仅改变了中间结点(mid)的位置。

思路

  1. 在斐波那契数列中找一个数F[k],使 F[k]-1 恰好大于或等于 顺序表的长度n。

  2. 若顺序表长度n小于这个F[k]-1,则将原顺序表的长度n扩展为 F[k]-1,并向其扩展后尾部的空缺值填充原顺序表中最后一个元素的值。

  3. mid不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F[k-1]-1(F代表斐波那契数列)

    F[k]=F[k-1]+F[k-2];由此可得(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1 ,刚好分成三部分,这个1表示的就是mid的位置,这也是为什么将顺序表长度扩展为 F[k]-1。

  4. 将要查找的值value与arr[mid]相比

    • value = arr[mid],mid位置的元素即为所要查找的值

    • value < arr[mid],在中间记录的左半区继续查找,high=mid-1;k=k-1;

    • value > arr[mid],在中间记录的右半区继续查找,low=mid+1;k=k-2;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package com.nanzx.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, 1234));
}

public static int[] fib() {
int[] fib = new int[maxSize];
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < fib.length; 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 k = 0;
int[] fib = fib();

while (arr.length > fib[k]-1) {
k++;
}

int[] temp = Arrays.copyOf(arr, fib[k]-1);
for (int i = high + 1; i < temp.length; i++) {
temp[i] = temp[high];
}

while (low <= high) {
mid = low + fib[k-1] - 1;
if (value < temp[mid]) {
high = mid - 1;
k--;
} else if (value > temp[mid]) {
low = mid + 1;
k = k - 2;
} else {
if (mid < arr.length) {
return mid;
} else {
return arr.length - 1;
}
}
}
return -1;
}
}

注意事项

折半查找是进行加法与除法运算(mid =(low +high)/2),

插值查找进行复杂的四则运算(mid = low+(high-low)*(key-a[low])/(a[high]-a[low]),

而斐波那契查找只是最简单的加减法运算(mid = low+F[k-1]-1),

在海量数据的查找过程中,这种细微的差别可能会影响最终的查找效率。