论坛 › 数据结构与算法 › 斐波那契查找

leelyn 发表于 2014-1-13 21:42:17

斐波那契查找

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

#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 = {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){
            continue;
      }else if(key >a){
            offs = idx;
            //--k;//这里可以优化算法一倍,不过加了会看不懂,就注释了
      }else
            return idx;
    }
    return -1;
}

int main(void)
{
    int a = {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;
}

查看完整版本: 斐波那契查找