【大话数据结构C语言】53 斐波那契查找（黄金分割法查找）

欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取精品学习资源 程序员技术交流①群：736386324 ，程序员技术交流②群：371394777    

和题目一样，这个算法是按照黄金分割法作为原理的

黄金分割就是0.618:1

 

先看下菲波那切数列

 

代码实现：

#include 

#define MAXSIZE 20

void fibonacci(int *f)
{
    int i;

    f[0] = 1;
    f[1] = 1;
    
    for(i=2; i < MAXSIZE; ++i)
    {
        f[i] = f[i-2] + f[i-1];

    }
}

int fibonacci_search(int *a,int key,int n)
{
    int low = 0;
    int high = n - 1;
    int mid = 0;
    int k = 0;
    int F[MAXSIZE];
    int i;

    fibonacci(F);
    
    while( n > F[k]-1 ) 
    {
        ++k;
    }

    for( i=n; i < F[k]-1; ++i)
    {
        a[i] = a[high];
    }

    while( low  key )
        {
            high = mid - 1;
            k = k - 1;
        }
        else if( a[mid] < key )
        {
            low = mid + 1;
            k = k - 2;
        }
        else
        {
            if( mid