斐波那契查找

leelyn

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

1. #include <stdio.h>
   
2. 
   
3. #define MAXSIZE 20
   
4. 
   
5. //a是测试数组,n是数组个数,key是搜索的值
   
6. int fi(int *a,int n,int key){
   
7.     register int k,idx,offs;
   
8.     static int prevn = -1,prevk = -1;
   
9. 
   
10.     const static int Fib[16] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};//可以自己重写,这里只是测试用
    
11.     if(n != prevn){
    
12.         int f0,f1,t;
    
13.         for(f0=0,f1=1,k=1;f1<n;++k){//得出测试数组在FIB中的位置
    
14.             t=f1;
    
15.             f1+=f0;
    
16.             f0=t;
    
17.         }
    
18.         prevk = k;
    
19.         prevn = n;
    
20. 
    
21.     }else{
    
22.         k = prevk;
    
23.     }
    
24. 
    
25.     for(offs=0;k>0;){
    
26.         idx = offs+Fib[--k];
    
27.         if(idx>=n || key<a[idx]){
    
28.             continue;
    
29.         }else if(key >a[idx]){
    
30.             offs = idx;
    
31.             //--k;//这里可以优化算法一倍,不过加了会看不懂,就注释了
    
32.         }else
    
33.             return idx;
    
34.     }
    
35.     return -1;
    
36. }
    
37. 
    
38. int main(void)
    
39. {
    
40.     int a[MAXSIZE] = {1,5,15,22,25,31,39,42,47,49,59,68,88,99,100,110,120,130,140};//这个是测试数组
    
41.     int pos;
    
42. 
    
43.     pos = fi(a,20,140);
    
44.     if(pos != -1){
    
45.         printf("%d\n",pos);
    
46.     }else{
    
47.         printf("-1");
    
48.     }
    
49.     return 0;
    
50. }

复制代码