// 斐波那契查找

#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 FibonacciSearch(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 main()
{
 int a[] = {0,16,24,35,47,59,62,73,88,99};
 int key=100;
 int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
 cout<<key<<" is located at:"<<index;
 return 0;
}