Fibonacci 数列
Fibonacci 数列，又称黄金分割数列，指的是这样一个数列：
1 1 2 3 5 8 13 21 ····
数学上，Fibonacci 数列递归定义：
F(1)=1，F(2)=1，F(n) = f(n-1) + F(n-2) （n>=2）
该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）
Fibonacci 查找
- 构建 Fibonacci 数列
- 扩展数组 a，用 a[n-1] 填充后面的数组
- mid = F[k-1] - 1，比较 temp[mid] 与 key
- key < temp[mid]，落在前半部分，k -= 1，待查找的数列长度变为 F[k-1]
- key > temp[mid]，落在后半部分，k -= 2，待查找的数列长度变为 F[k-2]
- key = temp[mid]，比较 mid 与 n，mid >= n 说明落在扩展的数列上，返回 n-1
与二分查找的区别
- 二分查找与 key 比较的数的下标： (left + right) / 2
- Fibonacci 查找与 key 比较的数的下标 F[k] - 1，都是 fibonacci 数列上的
因为 F[k] 表示元素个数，-1 之后才表示下标
#include <iostream>
using namespace std;
#define MAX_SIZE 20 // 斐波那契数组的长度，4181足够了
/**
* 斐波那契查找
* @param a: 要查找的数组
* @param n: 数组 a 的长度
* @param key: 要查找的关键字
* @return 要查找的 key 在数组中的下标
*/
int fibonacciSearch(const int *a, int n, int key) {
// 构建 Fibonacci 数列 F
int F[MAX_SIZE];
F[0] = 0;
F[1] = 1;
for (int i = 2; i < MAX_SIZE; ++i)
F[i] = F[i - 1] + F[i - 2];
// 在数列中寻找合适的数组长度 F[k]等于或刚刚大于n
int k = 2;
while (n > F[k]) ++k;
// 扩展数组a，并用 a[n-1] 填充后面的数组
int temp[F[k]];
for (int i = 0; i < n; ++i) temp[i] = a[i];
for (int i = n; i < F[k]; ++i) temp[i] = a[n - 1];
// 查找
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + F[k - 1] - 1; // 第F[k - 1]个数的下标
if (key < temp[mid]) { // 左边
high = mid - 1;
k -= 1; // F[k-1]是前半部分数组长度
} else if (key > temp[mid]) { // 右边
low = mid + 1;
k -= 2; // F[k-2]是后半部分数组长度
} else { // 相等，判断 mid 位置
if (mid < n)
return mid;
else
return n - 1;
}
}
return -1;
}
void printArray(const int *a, int len) {
for (int i = 0; i < len; ++i) {
cout << a[i] << " ";
}
cout << endl;
}
int main() {
int a[10] = {0, 16, 24, 35, 47, 59, 62, 73, 88, 99};
printArray(a, 10);
cout << "查找：";
int key;
cin >> key;
cout << "位置：" << fibonacciSearch(a, 10, key);
return 0;
}
0 16 24 35 47 59 62 73 88 99
查找：47
位置：4
