斐波那契查找原理详解与实现

最近看见一个要求仅使用加法减法实现二分查找的题目,百度了一下,原来要用到一个叫做斐波那契查找的的算法。查百度,是这样说的:

斐波那契查找与折半查找很相似,他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1,即n=F(k)-1;

 开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种

 1)相等,mid位置的元素即为所求

 2)>   ,low=mid+1,k-=2;说明:low=mid+1说明待查找的元素在[mid+1,hign]范围内,k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个,所以可以递归的应用斐波那契查找

 3)<    ,high=mid-1,k-=1;说明:low=mid+1说明待查找的元素在[low,mid-1]范围内,k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个,所以可以递归的应用斐波那契查找


大部分说明都忽略了一个条件的说明:n=F(k)-1, 表中记录的个数为某个斐波那契数小1。这是为什么呢?

我想了很久,终于发现,原因其实很简单:

是为了格式上的统一,以方便递归或者循环程序的编写。表中的数据是F(k)-1个,使用mid值进行分割又用掉一个,那么剩下F(k)-2个。正好分给两个子序列,每个子序列的个数分别是F(k-1)-1与F(k-2)-1个,格式上与之前是统一的。不然的话,每个子序列的元素个数有可能是F(k-1),F(k-1)-1,F(k-2),F(k-2)-1个,写程序会非常麻烦。

实现代码如下:

// 斐波那契查找.cpp   
  
#include "stdafx.h"  
#include <memory>  
#include  <iostream>  
using namespace std;  
  
const int max_size=20;//斐波那契数组的长度  
  
/*构造一个斐波那契数组*/   
void Fibonacci(int * F)  
{  
    F[0]=0;  
    F[1]=1;  
    for(int i=2;i<max_size;++i)  
        F[i]=F[i-1]+F[i-2];  
}  
  
/*定义斐波那契查找法*/    
int Fibonacci_Search(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字  
{  
  int low=0;  
  int high=n-1;  
    
  int F[max_size];  
  Fibonacci(F);//构造一个斐波那契数组F   
  
  int k=0;  
  while(n>F[k]-1)//计算n位于斐波那契数列的位置  
      ++k;  
  
  int  * temp;//将数组a扩展到F[k]-1的长度  
  temp=new int [F[k]-1];  
  memcpy(temp,a,n*sizeof(int));  
  
  for(int i=n;i<F[k]-1;++i)  
     temp[i]=a[n-1];  
    
  while(low<=high)  
  {  
    int mid=low+F[k-1]-1;  
    if(key<temp[mid])  
    {  
      high=mid-1;  
      k-=1;  
    }  
    else if(key>temp[mid])  
    {  
     low=mid+1;  
     k-=2;  
    }  
    else  
    {  
       if(mid<n)  
           return mid; //若相等则说明mid即为查找到的位置  
       else  
           return n-1; //若mid>=n则说明是扩展的数值,返回n-1  
    }  
  }    
  delete [] temp;  
  return -1;  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    int a[] = {0,16,24,35,47,59,62,73,88,99};  
    int key=100;  
    int index=Fibonacci_Search(a,sizeof(a)/sizeof(int),key);  
    cout<<key<<" is located at:"<<index;  
    system("PAUSE");  
    return 0;  
}  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

扫码关注云+社区

领取腾讯云代金券