Computer Science: 5th sem ADA Lab Program 1

Analysis and Design of Algorithms Lab.

Question 1.

//Implement Recursive Binary search and Linear search and determine the time required to search an element.

 #include <iostream>

 #include <conio.h>

 #include <time.h>

 using namespace std;

 int linearSearch(int *arr,int n,int index,int key)

 {

 if(index<n)

 {

 if(arr[index]==key)

 {

 return index;

 }

 return linearSearch(arr,n,index+1,key);

 }

 return -1;

 }

int binarySearch(int *arr,int low,int high,int key)//aascending order binary search

 {

 int mid=(low+high)/2;

 if(arr[mid]==key)

 return mid;

 if(arr[mid]>key)

 return binarySearch(arr,low,mid-1,key);

 return binarySearch(arr,mid+1,high,key);

 }
void main()

 {

 int n;

 cout<<"Enter the size of the array:";cin>>n;

 cout<<"Enter the array of size n in ascending order:";

 int *arr=new int[n];

 for(int i=0;i<n;i++)

 cin>>arr[i];

 cout<<"Enter the key value:";int key;cin>>key;



 cout<<"\nBinary searching...\n\n";

 int start=clock();

 int pos=binarySearch(arr,0,n-1,key);

 if(pos==-1)

 {

 cout<<"The key is not found";

 }

 else

 {

 cout<<"The key is found at "<<(pos+1);

 }

 int time1=(clock()-start)/CLK_TCK;


 cout<<"\nLinear searching...\n\n";

 start=clock();

 pos=linearSearch(arr,n,0,key);

 if(pos==-1)

 {

 cout<<"The key is not found";

 }

 else

 {

 cout<<"The key is found at "<<(pos+1);

 }

 int time2=(clock()-start)/CLK_TCK;
 cout<<"\n\nTime taken by binary search:"<<time1<<"\nTime taken by linear search:"<<time2;
 getch();

 }