与二分查找和插值查找的区别在于 分割的位置不同 利用了黄金分割的原理
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;
}
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。