Fibonacci Search

#include
<stdio.h>

#include
<conio.h>

int
a[15];

main()

{

int
i,lim,key,pos;

char
ans;

clrscr();

printf("\n\n\t\t\t
FIBONACCI SEARCH ");

printf("\n\t\t\t
~~~~~~~~~ ~~~~~~~");

printf("\n\n\t
Enter Array Limit :");

scanf("%d",&lim);

printf("\n\t
Enter Elements :\n");

for(i=0;i<lim;i++)

{

printf("\t\t\t");

scanf("%d",&a[i]);

}

Sort(a,lim);

do

{

printf("\nThe
Given values are :\n");

for(i=0;i<lim;i++)

printf("%d\t",a[i]);

printf("\n\t
Enter Key value to be Search :");

scanf("%d",&key);

pos=Fibsearch(a,lim,key);

if(pos==-1)

printf("\n\t
Value %d Not Found ",key);

else

printf("\n\t
Value %d Found At Position :%d ",key,pos+1);

printf("\n\n\tDo
you Continue (Y/N) :");

fflush(stdin);

scanf("%s",&ans);

}while(ans=='y' || ans =='y');

getch();

}

Sort(int *s,int n)

{

int
i,j,t;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(*(s+i) < *(s+j))

{

t=*(s+i);

*(s+i)=*(s+j);

*(s+j)=t;

}

}

int Fibsearch(int
*s,int n,int key)

{

int
k,m,i,p,q,t;

for(k=1;Fib(k)<n;k++);

i=Fib(k-1);

p=Fib(k-2);

q=Fib(k-3);

m=(n+1)-Fib(k);

if(key>s[i])

i=i+m;

while(i!=0)

{

if(key<s[i]) /* Key <
s[i] */

{

if(q==0)

i=0;

else

{

i=i-q;

t=p;

p=q;

q=t-q;

}

}

if(key==s[i]) /* Equal */

return(i);

if(key>s[i]) /* Key >
s[i] */

{

if(p==1)

i=0;

else

{

i=i+q;

p=p-q;

q=q-p;

}

}

}

/* End While */

return(-1);
/* if Not Found */

}

Fib(int n)

{

int
f1=-1,f2=1,f3=0,i;

for(i=1;i<=n;i++)

{

f3=f1+f2;

f1=f2;

f2=f3;

}

return(f3);

}