查找 --- 斐波那契

1. 引子

二分查找是进行加法与除法的运算 mid = (low +high)/2
插值查找是进行四则运算的 mid =( low + (high-low)*(key-a[low])/(a[high]-a[low])),
那么如何只使用简单的加减法运算来二分查找法呢？就引出了今天的斐波那契查找

2. 理论

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，即n=F(k)-1;

 开始将k值与第F(k-1）位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种

 1）相等，mid位置的元素即为所求

 2）>   ,low=mid+1,k-=2;说明待查找的元素在[mid+1,hign]范围内，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]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找

3. 代码

const int max_size = 15;

void FiboNach(int *F) {
    F[0] = 0;
    F[1] = 1;
    for (int i = 2; i < max_size; i++) {
        F[i] = F[i-1] + F[i-2];
    }
}

int Fibonaci_Search(int *a,int n, int key) {
    int low, high, mid, i, k;
    low = 0;
    high = n;
    k = 0;
    
    int F[max_size];
    FiboNach(F);
    
    while (n > F[k] - 1) {
        k++;
    }
    for (i = n; i < F[k]-1; i++) {
        a[i] = a[n];
    }
    while (low <= high) {
        mid = low + F[k-1] - 1;
        if (key < a[mid]) {
            high = mid - 1;
            k=k-1;
        } else if (key > a[mid]) {
            low = mid + 1;
            k = k-2;
        } else {
            if (mid <= n) {
                return mid;
            } else {
                return n;
            }
        }
    }
    return 0;
}

4. 推理

1.n=F(k)-1， 表中记录的个数为某个斐波那契数小1。这是为什么呢?

是为了格式上的统一，以方便递归或者循环程序的编写。表中的数据是F(k)-1个，使用mid值进行分割又用掉一个，那么剩下F(k)-2个。正好分给两个子序列，每个子序列的个数分别是F(k-1)-1与F(k-2)-1个，格式上与之前是统一的。不然的话，每个子序列的元素个数有可能是F(k-1)，F(k-1)-1，F(k-2)，F(k-2)-1个，写程序会非常麻烦

2.为什么在左侧k=k-1, 在右侧k=k-2呢？

对于二分查找，分割是从mid= (low+high)/2开始；而对于斐波那契查找，分割是从mid = low + F[k-1] - 1开始的； 通过上面知道了，数组a现在的元素个数为F[k]-1个，即数组长为F[k]-1，mid把数组分成了左右两部分(mid不包含在左右部分内)， 左边的长度为：（low + F[k-1] - 2）- low +1 = F[k-1] -1， 那么右边的长度就为（数组长-左边的长度-1）， 即：（F[k]-1） - ((F[k-1] )-1）-1 = F[k] - F[k-1] - 1  = F[k-2] - 1。

参考文章1
参考文章2