8.4.3　斐波那契查找

还有没有其他办法？我们折半查找是从中间分，也就是说，每一次查找总是一分为二，无论数据偏大还是偏小，很多时候这都未必就是最合理的做法。除了插值查找，我们再介绍一种有序查找，斐波那契查找（Fibonacci Search），它是利用了黄金分割原理来实现的。

斐波那契数列我们在前面4.8节讲递归时，也详细地介绍了它。如何利用这个数列来作为分割呢？

为了能够介绍清楚这个查找算法，我们先需要有一个斐波那契数列的数组，如图8-4-8所示。

8.4.3　斐波那契查找 - 图1

图8-4-8

下面我们根据代码来看程序是如何运行的。

  1. /* 斐波那契查找 */
  2. int Fibonacci_Search(int *a, int n, int key)
  3. {
  4.     int low, high, mid, i, k;
  5.     /*定义最低下标为记录首位 */
  6.     low = 1;                          
  7.     /*定义最高下标为记录末位 */
  8.     high = n;                         
  9.     k = 0;
  10.     /* 计算n位于斐波那契数列的位置 */
  11.     while (n > F[k] - 1)              
  12.         k++;
  13.     /* 将不满的数值补全 */
  14.     for (i = n; i < F[k] - 1; i++)    
  15.        a[i] = a[n];
  16.     while (low <= high)
  17.     {
  18.         /* 计算当前分隔的下标 */
  19.         mid = low + F[k - 1] - 1;     
  20.         /* 若查找记录小于当前分隔记录 */
  21.         if (key < a[mid])             
  22.         {
  23.             /* 最高下标调整到分隔下标mid-1处 */
  24.             high = mid - 1;           
  25.             /* 斐波那契数列下标减一位 */
  26.             k = k - 1;                
  27.         }
  28.         /* 若查找记录大于当前分隔记录 */
  29.         else if (key > a[mid])        
  30.         {
  31.             /* 最低下标调整到分隔下标mid+1处 */
  32.             low = mid + 1;            
  33.             /* 斐波那契数列下标减两位 */
  34.             k = k - 2;                
  35.         }
  36.         else
  37.         {
  38.             if (mid <= n)
  39.                 /* 若相等则说明mid即为查找到的位置 */
  40.                 return mid;           
  41.             else
  42.                 /* 若mid>n说明是补全数值，返回n */
  43.                 return n;             
  44.         }
  45.     }
  46.     return 0;
  47. }

1．程序开始运行，参数a={0,1,16,24,35,47,59,62,73,88,99}，n=10，要查找的关键字key=59。注意此时我们已经有了事先计算好的全局变量数组F的具体数据，它是斐波那契数列，F={0,1,1,2,3,5,8,13,21,……}。

8.4.3　斐波那契查找 - 图2

图8-4-9

2．第6～8行是计算当前的n处于斐波那契数列的位置。现在n=10，F[6]<n<F[7]，所以计算得出k=7。

3．第9～10行，由于k=7，计算时是以F[7]=13为基础，而a中最大的仅是a[10]，后面的a[11]，a[12]均未赋值，这不能构成有序数列，因此将它们都赋值为最大的数组值，所以此时a[11]=a[12]=a[10]=99（此段代码作用后面还有解释）。

4．第11～31行查找正式开始。

5．第13行，mid=1＋F[7-1]-1=8，也就是说，我们第一个要对比的数值是从下标为8开始的。

6．由于此时key=59而a[8]=73，因此执行第16～17行，得到high=7，k=6。

8.4.3　斐波那契查找 - 图3

图8-4-10

7．再次循环，mid=1＋F[6-1]-1=5。此时a[5]=47<key，因此执行第21～22行，得到low=6，k=6-2=4。注意此时k下调2个单位。

8.4.3　斐波那契查找 - 图4

图8-4-11

8．再次循环，mid=6＋F[4-1]-1=7。此时a[7]=62>key，因此执行第16～17行，得到high=6，k=4-1=3。

8.4.3　斐波那契查找 - 图5

图8-4-12

9．再次循环，mid=6＋F[3-1]-1=6。此时a[6]=59=key，因此执行第26～27行，得到返回值为6。程序运行结束。

如果key=99，此时查找循环第一次时，mid=8与上例是相同的，第二次循环时，mid=11，如果a[11]没有值就会使得与key的比较失败，为了避免这样的情况出现，第9～10行的代码就起到这样的作用。

斐波那契查找算法的核心在于：

1）当key=a[mid]时，查找就成功；

2）当key<a[mid]时，新范围是第low个到第mid-1个，此时范围个数为F[k-1]-1个；

3）当key>a[mid]时，新范围是第m+1个到第high个，此时范围个数为F[k-2]-1个。

8.4.3　斐波那契查找 - 图6

图8-4-13

也就是说，如果要查找的记录在右侧，则左侧的数据都不用再判断了，不断反复进行下去，对处于当中的大部分数据，其工作效率要高一些。所以尽管斐波那契查找的时间复杂也为O(logn)，但就平均性能来说，斐波那契查找要优于折半查找。可惜如果是最坏情况，比如这里key=1，那么始终都处于左侧长半区在查找，则查找效率要低于折半查找。

还有比较关键的一点，折半查找是进行加法与除法运算（mid=(low＋high)/2），插值查找进行复杂的四则运算（mid=low＋(high-low)*(key-a[low])/(a[high]-a[low])），而斐波那契查找只是最简单加减法运算（mid=low＋F[k-1]-1），在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。

应该说，三种有序表的查找本质上是分隔点的选择不同，各有优劣，实际开发时可根据数据的特点综合考虑再做出选择。