有序查找之：斐波那契(fibonacci)查找(C语言)

关于此算法的理解

斐波那契序列一些要牢记的知识点

序列从第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]);
    //    }
    /