Algorithm Fibonacci Search

Fibonacci search is an efficient search algorithm based on divide and conquer principle that can find an element in the given sorted array with the help of Fibonacci series in O(log N) time complexity. This is based on Fibonacci series which is an infinite sequence of numbers denoting a pattern which is captured by the following equation:F(n+1)=F(n)+F(n-1).

前言

    斐波那契搜索(Fibonacci search) ,又称斐波那契查找,是区间中单峰函数的搜索技术。斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n],将原查找表扩展为长度为Fn,完成后进行斐波那契分割,即F[n]个元素分割为前半部分F[n-1]个元素,后半部分F[n-2]个元素,找出要查找的元素在那一部分并递归,直到找到。

斐波那契搜索

斐波那契搜索基本思想:

斐波那契查找与折半查找很相似,他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1,及n=F(k)-1;开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种:
(1)相等,则mid位置的元素即为所求;
(2)>,则low=mid+1,k-=2;
说明:low=mid+1说明待查找的元素在[mid+1,high]范围内,k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))=Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个,所以可以递归的应用斐波那契查找。
(3))<,则high=mid-1,k-=1。
说明:low=mid+1说明待查找的元素在[low,mid-1]范围内,k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个,所以可以递归的应用斐波那契查找。
在最坏情况下,斐波那契查找的时间复杂度还是O(log2n),且其期望复杂度也为O(log2n),但是与折半查找相比,斐波那契查找的优点是它只涉及加法和减法运算,而不用除法,而除法比加减法要占用更多的时间,因此,斐波那契查找的运行时间理论上比折半查找小,但是还是得视具体情况而定。

斐波那契搜索解析:


斐波那契搜索代码:

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import java.util.Arrays;

/**
* @Auther: Arsenal
* @Date: 2020-03-23 11:29
* @Description: 斐波那契查找
*/
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, 8));// 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来循环处理,找到我们的数 key
while (low <= high) { // 只要这个条件满足,就可以找
mid = low + f[k - 1] - 1;
if(key < temp[mid]) { //我们应该继续向数组的前面查找(左边)
high = mid - 1;
//为甚是 k--
//说明
//1. 全部元素 = 前面的元素 + 后边元素
//2. f[k] = f[k-1] + f[k-2]
//因为 前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
//即 在 f[k-1] 的前面继续查找 k--
//即下次循环 mid = f[k-1-1]-1
k--;
} else if ( key > 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] - 1
k -= 2;
} else { //找到
//需要确定,返回的是哪个下标
if(mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
}

延伸

    斐波那契查找
    斐波那契搜索
    斐波那契查找原理解析
    韩顺平数据结构和算法
    Fibonacci Search - GeeksforGeeks

Content
  1. 1. 前言
  2. 2. 斐波那契搜索
  3. 3. 延伸