Fibonacci查找使用到的是黄金分割，改进二分法的轴点，选用黄金分割比来将查找表进行分割，逐渐迭代化简问题。之所以成为Fibonacci查找，是因为算法的实现与Fibonacci数列有着很大的关系。由于F[k] = F[k - 1] + F[k - 2]我们可以考虑将查找表分为

实现的代码

#include <stdio.h> #include <stdlib.h> #define LIST_SIZE 20 #define FIB_SIZE 20 typedef int KeyType; typedef char DataType[10]; typedef struct{ KeyType key; DataType data; }Node; typedef Node List[LIST_SIZE]; void GetFibonacci(int *Fib, int n) { int i; Fib[0] = 1; Fib[1] = 1; for (i = 2; i < n; ++i) Fib[i] = Fib[i - 1] + Fib[i - 2]; } /* 在[0, n)中查找key */ int FibSearch(List L, int n, KeyType key) { int Fib[FIB_SIZE]; int k, i; int lo = 0, hi = n - 1, mid; GetFibonacci(Fib, FIB_SIZE); k = 0; while (Fib[k] - 1 < n) k++; //将查找表扩充至[0, Fib[k] - 1) for (i = n; i < Fib[k] - 1; ++i) L[i].key = L[hi].key; hi = Fib[k] - 2; //查找 while (lo <= hi){ mid = lo + Fib[k - 1] - 1; if (L[mid].key == key){ return mid; } else if (key < L[mid].key){ //大头内 hi = mid - 1; k -= 1; } else{ //小头内 lo = mid + 1; k -= 2; } } return -1; } int main() { List L; KeyType key; KeyType a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int i, n = 10; for (i = 0; i < n; ++i) L[i].key = a[i]; printf("输入你需要查找的key: "); scanf("%d", &key); i = FibSearch(L, n, key); if (-1 == i){ printf("没有找到\n"); } else{ printf("找到了key, 在%d的位置\n", i); } system("pause"); return 0; }

---

需要注意的几点： 1. 注意在大头内F[k - 1] - 1中， 和小头内F[k - 2] - 1中迭代k的递减数是不同的 2. 在将查找表分块的时候，注意要将其扩容到F[k] - 1，这样才好定位好轴点mid