斐波那契查找

与二分查找和插值查找的区别在于 分割的位置不同 利用了黄金分割的原理

 

 

F[k]-1=F[k-1]-1 + mid +F[k-2]-1

所以要比较的是F[k]-1而不是F[k],这样能保证每次处理完后剩下的仍是F[i]-1

 

若待查找数组n！=F[K]-1，则扩充到F[K]-1

 

代码如下：

#include <iostream>
#include <math.h>
using namespace std;
void Fabonaci(int* f)
{
 f[0]=1;
 f[1]=1;
 for (int i=2;i<20;i++)
 {
  f[i]=f[i-1]+f[i-2];
 }
}
int search(int* f,int n,int k)
{
 int m_f[20]={0};
 Fabonaci(m_f);
 int j=0;
 while (n>(m_f[j]-1))
 {
  j++;
 }
 int i=0;
 for (i=n;i<(m_f[j]-1);i++)
 {
  f[i]=f[n-1];
 }
 int low=0,high=i,mid=0;
 while (low<=high)
 {
  mid=low+m_f[j-1]-1;
  if (f[mid]==k)
  {
   //若找到的位置大于最初数组元素的个数，则mid置为n-1，因为最初把数组以f[n-1]扩充到了m_f[j]-1
   if (mid>n-1)
   {
    mid=n-1;
   }
   return mid;
  }
  else if (f[mid]<k)
  {
   j=j-2;
   low=mid+1;
  }
  else
  {
   j=j-1;
   high=mid-1;
  }
 }
 return -1;
}

int main()
{     
 int s[20]={0,2,3,5,6,8,9,11,23,55,88,99,100,102,105,123,142,168,203,328};
 int k;
 while (cin>>k)
 {
  if (search(s,20,k)!=-1)
  {
   cout<<"位置为:"<<endl;
   cout<<search(s,20,k)<<endl;
  }
  else
  {
   cout<<"没有该值!"<<endl;
  }
 }
 return 0;
}