1 #include <stdio.h>  
 2   
 3 #define FIB_MAXSIZE 100  
 4   
 5 /** 
 6  * 生成斐波那契數(shù)列 
 7  * @param fib：指向存儲(chǔ)斐波那契數(shù)列的數(shù)組的指針 
 8  * @param size：斐波那契數(shù)列長(zhǎng)度 
 9  */  
10 void ProduceFib(int *fib, int size)  
11 {  
12     int i;  
13   
14     fib[0] = 1;  
15     fib[1] = 1;  
16   
17     for (i = 2; i < size; i++)  
18     {  
19         fib[i] = fib[i - 1] + fib[i - 2];  
20     }  
21 }  
22   
23 /** 
24  * 斐波那契查找，查找成功返回位序，否則返回-1 
25  * @param data：有序表數(shù)組 
26  * @param length：有序表元素個(gè)數(shù) 
27  * @param searchValue：待查找關(guān)鍵字 
28  */  
29 int FibonacciSearch(int *data, int length, int searchValue)  
30 {  
31     int low, high, mid, k, i, fib[FIB_MAXSIZE];  
32   
33     low = 0;  
34     high = length - 1;  
35   
36     ProduceFib(fib, FIB_MAXSIZE);  
37   
38     k = 0;  
39     // 找到有序表元素個(gè)數(shù)在斐波那契數(shù)列中最接近的最大數(shù)列值  
40     while (high > fib[k] - 1)  
41     {  
42         k++;  
43     }  
44   
45     // 補(bǔ)齊有序表  
46     for (i = length; i <= fib[k] - 1; i++)  
47     {  
48         data[i] = data[high];  
49     }  
50   
51     while (low <= high)  
52     {  
53         mid = low + fib[k - 1] - 1;   // 根據(jù)斐波那契數(shù)列進(jìn)行黃金分割  
54   
55         if (data[mid] == searchValue)  
56         {  
57             if (mid <= length - 1)  
58             {  
59                 return mid;  
60             }  
61             else  
62             {  
63                 // 說明查找得到的數(shù)據(jù)元素是補(bǔ)全值  
64                 return length - 1;  
65             }  
66         }  
67   
68         if (data[mid] > searchValue)  
69         {  
70             high = mid - 1;  
71             k = k - 1;  
72         }  
73   
74         if (data[mid] < searchValue)  
75         {  
76             low = mid + 1;  
77             k = k - 2;  
78         }  
79     }  
80   
81     return -1;  
82 }  
83   
84 int main()  
85 {  
86     int data[] = {1,3,5,7,9,11,13,15,17,19,21};  
87   
88     int index = FibonacciSearch(data, 11, 19);  
89     printf("%d\n", index);  
90   
91     return 0;  
92 }