斐波那契查找

leelyn

为小甲鱼的 斐波那契查找 进行补充,

#include <stdio.h>

#define MAXSIZE 20

//a是测试数组,n是数组个数,key是搜索的值
int fi(int *a,int n,int key){
    register int k,idx,offs;
    static int prevn = -1,prevk = -1;

    const static int Fib[16] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};//可以自己重写,这里只是测试用
    if(n != prevn){
        int f0,f1,t;
        for(f0=0,f1=1,k=1;f1<n;++k){//得出测试数组在FIB中的位置
            t=f1;
            f1+=f0;
            f0=t;
        }
        prevk = k;
        prevn = n;

    }else{
        k = prevk;
    }

    for(offs=0;k>0;){
        idx = offs+Fib[--k];
        if(idx>=n || key<a[idx]){
            continue;
        }else if(key >a[idx]){
            offs = idx;
            //--k;//这里可以优化算法一倍,不过加了会看不懂,就注释了
        }else
            return idx;
    }
    return -1;
}

int main(void)
{
    int a[MAXSIZE] = {1,5,15,22,25,31,39,42,47,49,59,68,88,99,100,110,120,130,140};//这个是测试数组
    int pos;

    pos = fi(a,20,140);
    if(pos != -1){
        printf("%d\n",pos);
    }else{
        printf("-1");
    }
    return 0;
}