1. Implement Recursive Binary search and Linear search and determine the time required to search an element. Repeat the experiment for different values of n, the number of elements in the list to be searched and plot a graph of the time taken versus n.

#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_tbegin,end;
clrscr();
while(ch)
{
printf("\n.......MENU.......\n 1.BinarySearch \n 2.Linear search \n 3.Exit \n");
printf("\n enter your choice\n");
scanf("%d",&op);
switch(op)
{
case 1:printf("\n enter the number of elments\n"); scanf("%d",&n);
printf("\n enter the number of an array in the order \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n enter 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\nUnsuccessful 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("\n enter the number of elements \n");
scanf("%d",&n);
printf("\n enter the elements of an array\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n enter the element 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("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("Invalid choice entered \n");
exit(0);
}
printf("\n Do you wish to run again(1/0) \n");
scanf("%d",&ch);
}
getch();
}
intbinsearch(intn,int a[],intk,intlow,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])
returnbinsearch(n,a,k,low,mid-1);
else
returnbinsearch(n,a,k,mid+1,high);
}
intlinsearch(intn,int a[],int k)
{
delay(1000); if(n<0) return -1;
if(k==a[n-1])
return (n-1);
else
returnlinsearch(n-1,a,k);
}