Program to Implement Recursive Binary search and Linear search

				
					/* Implementation of recursive binary search and sequential search */ 
#include<stdio.h>
#include<conio.h> 
#include<time.h> 
#include<stdlib.h>                       
#define max 20 int pos; 
int binsearch(int,int[],int,int,int); 
int linsearch(int,int[],int); 
void main() 
{
int ch=1; 
double t; 
int n,i,a[max],k,op,low,high,pos; 
clock_t begin,end; 
clrscr(); 
while(ch) 
{
printf("\n.....MENU.....\n 1.Binary Search\n 2.Linear     Search\n 3.Exit\n"); 
printf("\nEnter your choice\n");
scanf("%d",&op);
switch(op)   
{       
case 1:printf("\nEnter the number of elements \n"); 
scanf("%d",&n);
printf("\nEnter the elements of an array in order\n"); 
for(i=0;i<n;i++)        
scanf("%d",&a[i]);        
printf("\nEnter the elements to be searched\n");         
scanf("%d",&k);
low=0;high=n-1;
begin=clock(); 
pos=binsearch(n,a,k,low,high);
end=clock();
if(pos==-1) 
printf("\n\n Unsuccessful search");
else          
printf("\n Element %d is found at position %d",k,pos+1);
printf("\n Time taken is %lf CPU1 cycles\n",(end-begin)/CLK_TCK);
getch();
break;
case 2:printf("\nEnter the number of elements\n");         
scanf("%d",&n);         
printf("\nEnter the elements of an array\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nEnter the elements to be searched\n");
scanf("%d",&k);          
begin=clock(); 
pos=linsearch(n,a,k);
end=clock(); 
if(pos==-1)
printf("\n\n Unsuccessful search"); 
else            
printf("\n Element %d is found at position %d",k,pos+1);
printf("\n Time taken is %lf CPU cycles\n",(end-begin)/CLK_TCK);
getch();
break;
default:printf("\nInvalid choice entered\n");
exit(0);   
}    
printf("\n Do you wish to run again (1/0) \n");    
scanf("%d",&ch);    
} 
getch();
}
int binsearch(int n,int a[],int k,int low,int high)  
{
int mid; 
delay(1000);
mid=(low+high)/2;
if(low>high)
return -1; 
if(k==a[mid])
return(mid);
else      
if(k<a[mid])
return binsearch(n,a,k,low,mid-1);
else       
return binsearch(n,a,k,mid+1,high); 
}
int linsearch(int n,int a[],int k)   
{
delay(1000); 
if(n<0)
return -1;
if(k==a[n-1])
return(n-1);
else
return linsearch(n-1,a,k);     
}
				
			
Case 1

.....MENU.....

 1.Binary Search

 2.Linear Search

 3.Exit

Enter your choice

1

Enter the number of elements

3

Enter the elements of an array

4

8

12

Enter the elements to be searched

12

 Element 12 is found at position 2

 Time taken is 1.978022 CPU1 cycles

Case 2

.....MENU.....

 1.Binary Search

 2.Linear Search

 3.Exit

Enter your choice

2

Enter the number of elements

4

Enter the elements of an array

3

6

9

12

Enter the elements to be searched

9

Element 9 is found at position 3

 Time taken is 3.021978 CPU cycles                                     

Leave a Reply