Scribd
Upload
65 views2 pages

Binary Search and Linear Search

This document implements and compares recursive binary search and linear search algorithms. It includes code to generate random arrays of different sizes n, search for an element within the arrays, and measure the time taken. The time results are plotted against n to analyze and compare the search times of the two algorithms as the array size increases.

Uploaded by

ragunath
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
65 views2 pages

Binary Search and Linear Search

This document implements and compares recursive binary search and linear search algorithms. It includes code to generate random arrays of different sizes n, search for an element within the arrays, and measure the time taken. The time results are plotted against n to analyze and compare the search times of the two algorithms as the array size increases.

Uploaded by

ragunath
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

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);
}

You might also like