What is Fibonacci search? Please explain in detail?

Question

I want to know about this.

Answer 1

Fibonacci search is a search algorithm that applies to a sorted array. It makes use of a divide-and-conquer approach that can greatly reduce the time needed in order to reach the target element.

program:

#include<stdio.h>
void main()
{
   int n,a[50],i,key,loc,p,q,r,m,fk;
   clrscr();
   printf("\nenter number 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");
   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=rfibsearch(a,n,p,q,r,key);
   if(loc==0)
    printf("key is not found");
   else
    printf("%d is found at location %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 rfibsearch(int a[],int n,int p,int q,int r,int key)
{
   int t;
   if(p<1||p>n)
    return 0;
   else if(key==a[p])
    return p;
   else if(key<a[p])
  {
    if(r==0)
     return 0;
    else
    {
     p=p-r;
     t=q;
     q=r;
     r=t-r;
     return rfibsearch(a,n,p,q,r,key);
    }
   }
   else
   {
    if(q==1)
      return 0;
    else
    {
     p=p+r;
     q=q-r;
     r=r-q;
     return rfibsearch(a,n,p,q,r,key);
    }
   }
}