FIBONACCI SEARCH WITHOUT RECURSION BY USING C PROGRAM
Program:
#include<stdio.h>
void main()
{
int a[50],i,n,key,loc,fk,p,q,r,m;
clrscr();
printf("enter number of elements to be entered");
scanf("%d",&n);
printf("enter elements");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("enter the key element to search");
scanf("%d",&key);
fk=fib(n+1);
p=fib(fk);
q=fib(p);
r=fib(q);
m=(n+1)-(p+q);
if(key<a[p])
p=p+m;
loc=fibsearch(a,p,q,r,key);
if(loc==0)
printf("the key is not found");
else
printf("%d is found at %d",key,loc);
getch();
}
int fib(int m)
{
int a,b,c;
a=0;
b=1;
c=a+b;
while(c<m)
{
a=b;
b=c;
c=a+b;
}
return b;
}
int fibsearch(int a[],int p,int q,int r,int key)
{
int t;
while(p!=0)
{
if(key==a[p])
return p;
else if(key<a[p])
{
if(r==0)
p=0;
else
{
p=p-r;
t=q;
q=r;
r=t-r;
}
}
else
{
if(q==1)
p=0;
else
{
p=p+r;
q=q-r;
r=r-q;
}
}
}
return 0;
}
output:
