C Program for various searching methods

Saturday, 1 March 2014



#include <stdio.h>
#include <conio.h>
int fib(int n); // return a Fibonacci Number
int fibsearch(int a[],int key,int mid ,int p ,int q); //Fibonacci search function
int binsearch(int a[],int i ,int j,int key);/*Recursive binary search*/
int linsearch(int a[],int n , int key);
void main()
 {
   int a[30],key,mid,p,q,k,n,i,result,op;
   clrscr();
   do
      {
printf("\n1)Linear Search\n2)Binary Search\n3)Fibonacci Search");
printf("\n4)Quit");
printf("\nEnter Your Choice : ");
scanf("%d",&op);
switch(op)
    {
case 1: printf("\n Enter No. of elements : ");
scanf("%d" ,&n);
printf("\n Enter a  list of %d elements : ",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter the the element to be searched : ");
scanf("%d",&key);
result=linsearch(a,n,key);
if(result==-1)
      printf("\n Not found : ");
else
      printf("\n Found at location= %d",result);
break;

case 2: printf("\n Enter No. of elements : ");
scanf("%d" ,&n);
printf("\n Enter a sorted list of %d elements : ",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter the the element to be searched : ");
scanf("%d",&key);
result=binsearch(a,0,n-1,key);
if(result==-1)
      printf("\n Not found : ");
else
      printf("\n Found at location= %d",result);
break;

case 3: printf("\n Enter No. of elements : ");
scanf("%d" ,&n);
printf("\n Enter a sorted list of %d elements : ",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter the the element to be searched : ");
scanf("%d",&key);
//locate the kth term of Fibonacci series , such that fib(k) > n
for(k=1 ; fib(k) <= n ; k++)
;
p=fib(k-2);
q=fib(k-3);
mid=n-p+1;
result=fibsearch(a,key,mid,p,q);
if(result==-1)
      printf("\n Not found : ");
else
      printf("\n Found at location= %d",result);
break;

     }
      }while(op!=4);
 }

 int fib(int n)
  { if(n==0) return(0);
    if(n==1)    return(1);
    return(fib(n-1)+fib(n-2));
  }

int fibsearch(int a[],int key,int mid ,int p ,int q)
   {
       int temp;

       if(key==a[mid])
 return(mid);
       if(key> a[mid])
 {
    if(p==1)
return(-1);

    mid=mid+q;  // new mid
    p=p-q;      //p=fib(k-4)
    q=q-p;      //q=fib(k-5)
    return(fibsearch(a,key,mid,p,q));
 }
       else    //key < a[mid]
 {
    if(q==0)
return(-1);
    mid=mid-q;    // new mid
    temp=p-q;
    p=q;         //p=fib(k-3)
    q=temp;      //q=fib(k-4)
    return(fibsearch(a,key,mid,p,q));
 }
    }

int binsearch(int a[],int i, int j,int key)
{
   int c;
   if(i>j)
    return(-1);
   c=(i+j)/2;
   if(key==a[c])
       return(c);
   if(key>a[c])
       return(binsearch(a,c+1,j,key));
   return(binsearch(a,i,c-1,key));
 }
int linsearch(int a[],int n , int key)
{
    int i;
    for(i=0;i<n;i++)
      {
if(a[i]==key)
    return(i);
      }

   return(-1);
}


OUTPUT:-

1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 1

 Enter No. of elements : 4

 Enter a  list of 4 elements : 23 34 8 96

 Enter the the element to be searched : 8

 Found at location= 2
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 1

 Enter No. of elements : 3

 Enter a  list of 3 elements : 12 34 3

 Enter the the element to be searched : 12

 Found at location= 0
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 2
 Enter No. of elements : 4

 Enter a sorted list of 4 elements : 4 8 27 90

 Enter the the element to be searched : 5

 Not found :
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 2

 Enter No. of elements : 3

 Enter a sorted list of 3 elements : 5 6 89

 Enter the the element to be searched : 5

 Found at location= 0
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 3

 Enter No. of elements : 4

 Enter a sorted list of 4 elements : 2 13 34 78

 Enter the the element to be searched : 13

 Found at location= 1
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 4

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...
Related Posts Plugin for WordPress, Blogger...
 

Most Reading

Labels