//PROGRAM CODE 9.5 // Function to find nth Fibonacci number
#include<iostream.h>
#include<conio.h>
#define max 20

int fibo(int n)
{
if(n==0 || n==1)
return 1;
else
return(fibo(n-1)+fibo(n-2));
}
// Function for Fibonacci search
int Fibonacci_Search(int A[],int n, int key)
{
int f1,f2,t,mid,j,f;
j=1;
while(fibo(j) <= n)
{ //find fib(j) such that fib(j)>=n
j++;
}
f=fibo(j);
f1=fibo(j-2); //find lower Fibonacci numbers
f2=fibo(j-3); // f1=fib(j-2), f2=fib(j-3)
mid=n-f1+1;
while(key!=A[mid]) // if not found
{
if(mid<0||key>A[mid])
{ //look in lower half
if(f1 == 1)
return -1;
mid = mid+f2; //decrease Fibonacci numbers
f1 = f1-f2;
f2 = f2-f1;
}
else
{ //look in upper half
if(f2 == 0) //if not found return -1
return -1;
mid = mid-f2; //decrease fibonacci numbers
t = f1-f2; //this time, decrease more
f1 = f2; //for smaller list
f2 = t;
}
}
return mid;
}

void main()
{
int A[max], ele,size,i,ans;
clrscr();
cout<<"\n\n Eneter the size of the array:";
cin>>size;
cout<<"\n\n Enter elements:\n";
for (i=0;i<size;i++)
{
cin>>A[i];
}
cout<<"\n\n Enter the element to be search = ";
cin>>ele;

ans=Fibonacci_Search(A,size,ele);

if(ans!=-1)
	cout<<"\tElement "<<ele<<" found at position "<<ans+1;
else
	cout<<"\tElement "<<ele<<"  Not found in the given array.";
       getch();
}
/*********************OUTPUT*********************************
 Eneter the size of the array:5

 Enter elements:
2 3 4 5 6
 Enter the element to be search = 7
	Element 7  Not found in the given array.

 Eneter the size of the array:5

 Enter elements:
1 2 3 4 5

 Enter the element to be search = 4
	Element 4 found at position 4
************************************************************/