I have to write a C++ program that randomly generates the numbers 1-100 in an ar
ID: 3835274 • Letter: I
Question
I have to write a C++ program that randomly generates the numbers 1-100 in an array and then I have to find the number 77 using the sequential search and computer O(n). After that the program needs to find the number 77 using a binary serach. Before computing the binary search, you can use the number using any one of the sort algorithm. Computer O(n). Then the program has to display the times it took to search and find the 77 for both the sequential and binary search method. Lastly compare both O(n) and conclude the results(which algorith performs best and why)
Explanation / Answer
Binary search is the best algorithm for searching with time compleity O(log n) where n is the number of elements provided the array must be sorted.Every time when we comapre the number with middle element, the search space reduced to half.Whereas linear alogrithm comapre with everey element in worst case.
#include<iostream>
#include<time.h>
#include<algorithm>
using namespace std;
#define MAX 100
//search an element lenearly which takes O(n)
bool linear_search(int a[],int num)
{
for(int i=0;i<MAX;i++)
{
if(a[i]==num)
return true;
}
return false;
}
//binary search
void binary_search(int a[],int num)
{
int l=0,h=MAX-1,mid;
while(l<h)
{
mid=(l+h)/2;
if(a[mid]==num) //comapring with the middle elements
{
cout<<"Element is found by binary search ";
return ;
}
if(a[mid]>num)
h=mid-1;
else
l=mid+1;
}
}
int main(int argc,char **argv)
{
int a[MAX];
bool flag;
int num=77; //number to search
clock_t startl,endl,startb,endb; //measuring the time of execution
srand(time(NULL));
for(int i=0;i<MAX;i++)
{
a[i]=rand()%100+1;
}
startl=clock();
flag=linear_search(a,num);
endl=clock();
if(flag==false)
{
cout<<"Element is not present in the array";
exit(0);
}
cout<<"Element is found in the array by linear search";
startb=clock();
//sort the array for binary search
sort(a,a+MAX);
binary_search(a,num);
endb=clock();
cout<<" Leanear search takes "<<((float)(endl-startl)/CLOCKS_PER_SEC)<<"secs"<<endl;
cout<<" Binary search takes "<<((float)(endb-startb)/CLOCKS_PER_SEC)<<"secs"<<endl;
return 0;
}