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

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

    为了能够介绍清楚这个查找算法，我们先需要有一个斐波那契数列的数组，如图8-4-8所示。
    image.png
    下面我们根据代码来看程序是如何运行的。

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

    image.png

    1. 第6～8行是计算当前的n处于斐波那契数列的位置。现在n=10，F[6]<n<F[7]，所以计算得出k=7。
    2. 第9～10行，由于k=7，计算时是以F[7]=13为基础，而a中最大的仅是a[10]，后面的a[11]，a[12]均未赋值，这不能构成有序数列，因此将它们都赋值为最大的数组值，所以此时a[11]=a[12]=a[10]=99（此段代码作用后面还有解释）。
    3. 第11～31行查找正式开始。
    4. 第13行，mid=1＋F[7-1]-1=8，也就是说，我们第一个要对比的数值是从下标为8开始的。
    5. 由于此时key=59而a[8]=73，因此执行第16～17行，得到high=7，k=6。

    image.png

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

    image.png

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

    image.png

    1. 再次循环，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个。

    image.png
    也就是说，如果要查找的记录在右侧，则左侧的数据都不用再判断了，不断反复进行下去，对处于当中的大部分数据，其工作效率要高一些。所以尽管斐波那契查找的时间复杂也为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），在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。

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