序列从第3个值开始，其值等于前2个值的和
? 即某值下标为k，则F[k] = F[k-1] + F[k-2]
相临的序列的值 前面的值/后面的值会越来越接近0.618黄金分割点
既然二分查找法可以找到一个序列的0.5的位置进行查找，那么斐波那契也可以使用它的黄金分割点0.618位置应用于序列查找（如果有白银分割点0.718那么也可能也会有白银查找法）
相比二分查找，该算法的优势是在求mid值的时候使用的只是加减法，在数量较大时会提高效率
根据待查询数组的查询长度(以下简称查询长度)，生成斐波那契序列数组，且该序列的值一定要把查询长度包含进来，也就是说比如查询长度为n，则斐波那契序列只要满足最后一个下标的值F[k], n <= f[k]就可以，太长无用，序列第1个值是不是0无所库（本次实现直接手动创建fibonacci）
拉下来根据待查询数组的查询长度n匹配斐波那契序列，获取关键下标k，有两种情况：
? n 正好是有效的斐波那契序列中的数字n = F[k]，直接返回所在下标k
? n 不是有效非斐波那契序列数字n < F[k]，同样返回k，只是出现这种情况后原数组需要把查询长度扩充到k的长度才以进行查询，新扩充的位置用待查询数组的最后一个元素填充
F[k-1] 和 F[k-2] 两者的数量正好是被查询数组使用黄金分割点后的两部分
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int fibonacci(int *, int, int);
int fibonacci(int *a, int n, int key)
{
int low, high, mid, k;
low = 1;
high = n;
// 为了代码简化直接手动创建fibonacci序列数组，如果代码动态生成则只要序列的最后1个值>=n即可
// 此数组的值第1个元素是0还是1感觉影响不大
int F[] = {0, 1, 1, 2, 3, 5, 8, 13}; // 这些值可以理解为使用fibonacci分割了查询长度
k = 0;
while (n > F[k]) { // 书为为n > F[k] - 1，但是感觉不需要，如果加上-1, n=8那么k最终为7 值13，完全用不上
k++; // 返回下标7, 值为13, 8 < 10 < 13 向后取大
}
// 如果F[k]>n，则a数据扩容(扩容后的长度等于F[k] + 1,1为待查询数组不使用0下标)
if (F[k] > n) {
a = realloc(a, sizeof(int) * (F[k]+1));
for (int i=n+1; i<=F[k]; i++) { // 11, 12, 13执行3次,填充新的数组元素
a[i] = a[n];
}
}
// 下面这段可以去掉注释看效果
//if (F[k] > n) {
// printf("a数组查询长度需要扩展到 %d\n", F[k]);
// for (int i=0; i<=F[k]; i++) { // 下标14已经无效，这里为了看效果
// printf("a[%d]=%d\n", i, a[i]);
// }
//}
//else
// printf("a数组无需扩展\n");
// 开始查找
while (low <= high) {
/* 关于下面这行的解释
* low, 不用多说本次查询的起始下标
* F[k-1], 因为F[k] = F[k-1] + F[k-2], F[k-1]/F[k]接近0.618，也就是要找的黄金分割点
* -1, 因为F[k] = F[k-1] + F[k-2], 也就是说分为了两端，F[K-1]占到了F[k]的0.618也就是大半部分，
* F[k-2]占了小部分，这两部分的顺序不要纠结，只知道数量或长度即可，low + F[k-1]如果不减1，则
* 会越界到F[k-2]的这一部分，因为low下标本身也要被查找
*/
mid = low + F[k-1] -1;
if (key < a[mid]) { // key在F[k-1]的部分,假设这部分在整体左边(好理解)，F[k-1]可以只理解为这部分的数量）
high = mid - 1; // 移动high， 此时缩小的范围 low~high在F[k-1]下标范围内
k = k - 1; // 下一轮查找的数组范围的fibonacci基数，和第1次找k一个道理
}
else if (key > a[mid]) {
low = mid + 1; // key在F[k-2]小部分，按照公式F[k] = F[k-1] + F[k-2]，所以这部分的长度为F[k-2]
k = k-2; // 下一轮查找F[k-2]这部分范围(找黄金分割点)的基数
}
else { // 查找成功
if (mid <= n)
return mid; // 在a扩展前的范围内匹配到
else
return n; // 在a扩展后的范围内匹配到，后面的值都是用n下标值填充的，所以返回n
}
}
return 0;
}
int main(void)
{
int data[11] = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99}; // 0下标未使用, 所以查询长度为10（1~10）
// 拷贝data到a，让a支持扩展内存
int *a;
a = (int *)malloc(sizeof(int)*11);
memcpy(a, data, sizeof(int)*11);
printf("查找 59 的下标(0为未找到): %d\n", fibonacci(a, 10, 59));
printf("查找 99 的下标(0为未找到): %d\n", fibonacci(a, 10, 99));
printf("查找 15 的下标(0为未找到): %d\n", fibonacci(a, 10, 15));
printf("查找 0 的下标(0为未找到): %d\n", fibonacci(a, 10, 0));
// 如果进行下面这种查询，还需要做额外的修改，暂时不考虑这些场景
//printf("在前4个元素 查找 59 的下标(0为未找到): %d\n", fibonacci(a, 4, 59));
return 0;
}
output
[root@8be225462e66 c]# gcc fibonacci.c && ./a.out
查找 59 的下标(0为未找到): 6
查找 99 的下标(0为未找到): 10
查找 15 的下标(0为未找到): 0
查找 0 的下标(0为未找到): 0
[root@8be225462e66 c]#原文：https://blog.51cto.com/sndapk/2726678