有序查找（折半查找、插值查找、斐波那契查找）的三个方法都是按照一定的分割比例进行查找，折半查找是对半分割，插值查找是靠近分割，斐波那契查找是黄金分割。

斐波那契数列

斐波那契数列（Fibonacci sequence）：又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

黄金分割：黄金分割是指将整体一分为二，较大部分与整体部分的比值等于较小部分与较大部分的比值，其比值约为 0.618。这个比例被公认为是最能引起美感的比例，因此被称为黄金分割。

算法核心

算法要求数据个数: n=F[k]-1, 分割点：mid=low+F[k-1]-1.

查找的数据 key，和数组 mid 位置的数据对比结果如下：

1. 相等，查找成功；

2. 小于，则 high = mid-1，k-=1;

说明：如图所示，high = mid-1 说明 key 的值可能在[low，mid-1]之间，k-=1 说明在[low，mid-1]之间有 F[k-1]-1 个元素；

1. 大于，则 low = mid+1，k-=2；

说明：如图所示，low = mid+1 说明 key 的值可能在[mid+1，high]之间，k-=2 说明在[mid+1，high]之间有 F[k-2]-1 个元素；

关于 F[k]-1:由斐波那契数列的公式可知，F[k]=F[k-1]+F[k-2]，那么 F[k]-1=(F[k-1]-1)+(F[k-2]-1)+1，所以数组长度只需要满足 F[k]-1，就可以把数组分为 F[k-1]-1 和 F[k-2]-1 左右两部分，mid=low+F[k-1]-1。

代码

C 语言实现：

#include <stdio.h>#include <math.h>
#define MAXSIZE 50 /*存储空间初始分配量*/

int F[50]; /*斐波那契数列*/

/*斐波那契查找*/int Fibonacci_Search(int *a, int n, int key){    int low,high,mid,i,k = 0;    low = 1;    high = n;    while(n > F[k]-1)    {          k++;     }    for (i = n; i < F[k]-1; i++)    {        a[i]=a[n];    }    while (low <= high)    {        mid = low + F[k-1] -1;        if(key < a[mid])        {            high = mid - 1;            k = k - 1;        }        else if (key > a[mid])        {            low = mid + 1;            k = k - 2;        }         else        {            if(mid <= n)                return mid;            else                return n;        }       }    return 0;}
int main() {    int result;    int arr[MAXSIZE]={0,1,16,24,35,47,59,62,73,88,99};
    //斐波那契    int i;    F[0] = 0;    F[1] = 1;    for (i = 2; i < MAXSIZE; i++)    {        F[i] = F[i-1] + F[i-2];    }    result = Fibonacci_Search(arr, 10, 62);    printf("Fibonacci_Search:%d \n", result);
    return 0;}

对比

斐波那契查找的时间复杂度为 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)，在海量数据的查找过程中，这种细微差别可能会影响最终的查询效率。

注意： 折半查找计算 mid 为了放值溢出，推荐使用(mid=low+(high-low)/2)。

成长快乐，成长快乐，成长快乐

参考：

《大话数据结构》

查找--斐波那契查找

七大查找算法