本文共 3376 字，大约阅读时间需要 11 分钟。

要说斐波拉契搜索就必须要先说一下什么 是斐波拉契数列：

斐波拉契数列：

F(1)=1， F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*） 就是从第三项开始，每一项都等于前两项的和。

费氏搜寻法简介：

费氏搜寻法，就是利用斐波拉契数列从有序数列中搜寻特定元素的一种搜索算法，它的前提是数列必须要有序。我们熟悉的二分查询，每次搜寻的时候，都会讲区间分为两半，所以其搜寻时间为O(log(2)n)，这边要介绍的费氏搜索，其利用费氏数列中的数作为间隔来搜寻下一个数，所以区间收敛的速度会更快，搜索时间为O(logn)。

用一个例子来说明：

查询的数组：num[]

0 0 1 1 1 2 2 2 3 5 6 7 8 8 9 斐波拉契数列：F[] 1 1 2 3 5 8 13 21…

现在假定我们查询的数字是：find=7.

方便计算，我们的num[]和F[]的数组下标都从1开始。 首先，可以知道数组num长度n=15,先找到（尽可能大的）小于等于15的F[x]=13，他的下标x=7,此时还需要一个公式：F[x]+m=n,所以m=15-13=2; x,m,F[x]在一开始数组长度知道的情况下就可以知道了。

第一次搜索：

不是从x=7,开始查询的，而是x–,i=x=6开始查询的，如果num[6]<7,这时候，i+=m,第二次搜索的时候就从第8个开始。（如果num[6]>7,则i是i-=F[x]） i=6 num[6]=2<7 i+=2

第二次搜索：

第二次搜索就从上一次 得出的i=8开始搜索，这时候，num[8]=2<7,这时候i的变化不再是加减m了，而是加减斐波拉契数列的值（F[x]）了。num[i]小于我们要查找的数值，i就加斐波拉契数列的值，反之则减. i=8 num[8]=2<7 i+=F[–x] 即i+=F[5] i=8+5=13

第三次搜索

i=13 num[13]=8>7 i-=F[–x] 即i-=F[4] i=13-3=10

第四次搜索：

i=10 num[10]=5<7 i+=F[–x] 即i+=F[3] i=10+2=12

第五次搜索：

i=12 num[12]=7 这样就找到我们要查找的数值7，他是索引12.

总结：

费氏搜寻会先透过公式计算求出第一个要搜寻数的位置,F[x]+m=n，计算出F[x],m,x的值，用费氏数列作为间隔来搜寻下一个数，区间收敛的速度更快，同时本身只会用到加减法，在运算上也可以加快。

代码：

#include
   
    #include
    
     #include
     
      #define MAX 15#define SWAP(x,y) {int t; t = x; x = y; y = t;} void createfib(void);               // 建立费氏数列int findx(int);                     // 找x值int fibsearch(int[], int);          // 费氏搜寻void quicksort(int[], int, int);    // 快速排序 int Fib[MAX] = {-999};//主程序（C/OC）int main(void){int number[MAX] = {0};int i, find; srand(time(NULL)); for(i = 1; i <= MAX; i++) {     //产生随机数列    number[i] = rand() % 10;} quicksort(number, 1, MAX);      //快速排序 printf("数列：");                //打印排序后的数列for(i = 1; i <= MAX; i++)    printf("%d ", number[i]);find = 7;                      //要寻找的对象if((i = fibsearch(number, find)) >= 0)    printf("找到数字于索引 %d ", i);else    printf("\n找不到指定数"); printf("\n"); }//建立费氏数列，总共求得MAX+1个斐波那契数void createfib(void) {    int i;    Fib[0] = 0;    Fib[1] = 1;        for(i = 2; i < MAX; i++)        Fib[i] = Fib[i-1] + Fib[i-2];} //找x值int findx(int n) {    int i = 0;    while(Fib[i] <= n)        i++;    i--;    return i;//找到第i个Fib元素小于等于MAX+1} //费式搜寻int fibsearch(int number[], int find) {    int i, x, m;        createfib();                    //创建斐波那契数列        x  = findx(MAX+1);              //斐波那契数列中第x个数刚好不大于MAX+1。MAX是确定的，所以比较的起始点是确定的。    m = MAX - Fib[x];               //得到一个较小的差值。m的值也是确定的。    printf("\nx = %d, m = %d, Fib[x] = %d\n\n",           x, m, Fib[x]);        x--;        i = x;        if(number[i] < find)            //i的初值也是确定的。        i += m;        while(Fib[x] > 0) {             //搜寻，x值不断减小，范围越来越小，搜寻越来越精细        if(number[i] < find)        //小于被搜寻的值            i += Fib[--x];          //右移搜寻位置        else if(number[i] > find)   //大于被搜寻值            i -= Fib[--x];          //左移搜寻位置        else            return i;               //相等，找到    }    return -1;                      //搜寻步子已经最小，还是没找到，搜寻结束} //快速排序void quicksort(int number[], int left, int right) {    int i, j, k, s;        if(left < right) {        s = number[(left+right)/2];        i = left - 1;        j = right + 1;                while(1) {            while(number[++i] < s) ;        // 向右找            while(number[--j] > s) ;        // 向左找            if(i >= j)                break;            SWAP(number[i], number[j]);        }                quicksort(number, left, i-1);       // 对左边进行递回        quicksort(number, j+1, right);      // 对右边进行递回    } }
     
    
   

运行结果：

转载地址：http://biyen.baihongyu.com/