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

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

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

黄金分割就是0.618:1

先看下菲波那切数列

代码实现：

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #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 <= high )
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              mid = low + F[k-1] - 1;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        if( a[mid] > key )
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  high = mid - 1;
     
    
   

    

     

    
    

     

                  k = k - 1;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        else if( a[mid] < key )
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  low = mid + 1;
     
    
   

    

     

    
    

     

                  k = k - 2;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        else
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            if( mid <= high ) 
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     
                return mid;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     
            else
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     
                return high;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    return -1;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
    int a[MAXSIZE] = {1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88};
     
    
   

    

     

    
    

     
    int key;
     
    
   

    

     

    
    

     
    int pos;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    printf("请输入要查找的数字:");
     
    
   

    

     

    
    

     
    scanf("%d", &key);
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     

          pos = fibonacci_search(a, key, 13);
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
    if( pos != -1 )
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        printf("\n查找成功，关键字 %d 所在的位置是: %d\n\n", key, pos);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    else
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        printf("未在数组中找到元素:%d\n\n", key);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
        
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。

原文链接：allen5g.blog.csdn.net/article/details/116885746