USA: +1 (725) 712-1730 
Sign in
For this computer assignment, you are to write and implement a C++ program to implement two search algorithms ( a linear search and a binary search) on randomly generated integers stored in vectors.
Put the implementations of your subroutines (described below) in your source file sub2.cc and their prototypes in your header file prog2.h.
void Vectors ( vector < int >& v1, vector < int >& v2, int s1, int s2 ) : Fills the elements of vectors v1 of size ARR_SIZE = 200 and v2 of size TEST_ARR_SIZE = 100 with random numbers, generated by two sets of pseudo–random numbers with the seed values s1 and s2, where s1 (defined as SEED1 = 1) is for v1and s2 (defined as SEED2 = 3) is for v2. To initiate a random number generator (RNG) with the seed value seed, execute the system function srand ( seed ) (only once), and to generate a random integer in the range [ LOW = 1, HIGH = 1000 ], execute: rand ( ) % ( HIGH – LOW + 1 ) + LOW.
bool linearSearch ( const vector < int >& v, int x ) : A linear search algorithm, where x is the searched item in vector v. It simply starts searching for x from the beginning of vector v to the end, but it stops searching when there is a match. If the search is successful, it returns true; otherwise, it returns false. To implement this routine, simply call the find ( ) function in the STL.
bool binarySearch ( const vector < int >& v, int x ) : A binary search algorithm, where x is the searched item in vector v. If the search is successful, it returns true; otherwise, it returns false. To implement this routine, simply call the binary_search ( ) function in the STL.
int search ( const vector < int >& v1, const vector < int >& v2, bool (*p ) ( const vector < int >&, int ) ) : A generic search algorithm – takes a pointer to the search routine p ( ), and then it calls p ( ) for each element of vector v2 in vector v1. It computes the total number of successful searches and returns that value to the main ( ) routine as an input argument to the print routine printStat ( ), which is used to print out the final statistics for a search algorithm.
void sortVector ( vector < int >& v ) : A sort algorithm to sort the elements of vector v in ascending order. To implement this routine, simply call the sort ( ) function in the STL.
void printVector ( const vector < int >& v ) : Prints the contents of vector v on stdout, up to NO_ITEMS = 16 items on a single line except perhaps the last line. The sorted numbers need to be properly aligned on the output. For each printed number, allocate ITEM_W = 4 spaces for each item.
void printStat ( int totalSucCnt, int vectorSz ) : Prints the percent of successful searches as right-aligned, floating-point numbers on stdout, where totalSucCnt is the total number of successful comparisons and vectorSz is the size of the test vector.
Expert Answer
//sub2.cpp
#include<iostream>
#include<vector>
#include<stdlib.h>
using namespace std;
//
void Vectors(vector < int >& v1, vector < int >& v2, int s1, int s2 )
{
int i;
//filling vector v1
for(i=0;i<200;i++)
{
v1.push_back(1+(rand()%s1));//seed1 is 1,seed2 is s1
}
//filling vector v2
for(i=0;i<100;i++)
{
v2.push_back(1+(rand()%s2));//seed1 is 1, seed2 is s2
}
}
bool linearSearch ( const vector < int >& v, int x )
{
int i;
int n =v.size();//finding size of vector
for(i=0;i<n;i++)
{
if(x==v.at(i))return true;//if found returning true,,
}
//if not found
return false;//returing false
}
bool binarySearch ( const vector < int >& v, int x )
{
int n =v.size();//finding size of vector
int left= 0, right =n;
int mid;
while (left < right) {
mid = left + (right – left)/2;
if (x > v[mid]){
left = mid+1;
}
else if (x < v[mid]){
right = mid;
}
else {
return true;
}
}
//if not found
return false;//returing false
}
void sortVector ( vector < int >& v )
{
int i,j,temp;
int n =v.size();
//sorting vector using bubble sort technique
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(v.at(i)<v.at(j))//sorting in ascending order
{
//swapppinh…
temp = v.at(i);
v[i]=v.at(j);
v[j]=temp;
}
}
}
}
void printVector ( const vector < int >& v )
{
int i,n =v.size();
for(i=0;i<n;i++)
{
cout<<v.at(i)<<” “;
}
cout<<“n”;
}
void printStat ( int totalSucCnt, int vectorSz )
{
float f = vectorSz;
f = totalSucCnt/f;
f = f*100;
cout<<“The percentage of successful searches : “<<f<<“%n”;
}
//testing function….
int main()
{
vector<int> v1,v2;
//calling vectors functions
Vectors(v1,v2,40,20);
//printing vectors..
cout<<“printing vector v1:n”;
printVector(v1);
cout<<“printing vector v2:n”;
printVector(v2);
//linear search on vector v1:
cout<<“Searching element 10 linearly…in v1 :”;
if(linearSearch(v1,10))
{
cout<<“Foundn”;
}
else
{
cout<<“Not foundn”;
}
//sorting function..
sortVector(v2);//sorting vector v2
cout<<“printing vector v2 after sorting:n”;
printVector(v2);
cout<<“Searching element 5 Binary search…in v2 :”;
if(binarySearch(v2,5))
{
cout<<“Foundn”;
}
else
{
cout<<“Not foundn”;
}
return 0;
}
output:-
printing vector v1:
2 28 15 21 10 5 39 39 3 25 26 26 2 28 2 12 36 23 28 37 32 5 23 34 13 23 22 37 39 16 8 7 12 19 30 33 28 20 36 15 24 12 3 14 34 25 22 32 14 29 28 5 23 38 38 20 4 22 10 19 37 36 31 3 9 27 1 23 25 9 7 6 11 10 11 31 7 22 34 29 30 24 5 35 37 1 7 17 12 29 25 40 27 4 18 19 39 3 10 22 34 36 40 19 25 11 18 27 34 27 22 26 5 33 31 30 18 14 18 33 27 11 2 37 36 8 16 15 32 13 31 31 22 5 7 31 28 32 8 18 18 8 34 24 26 30 10 39 22 29 23 27 27 31 14 9 21 32 3 16 11 40 25 18 29 4 36 2 3 31 12 37 15 21 37 22 29 40 29 5 2 15 14 40 19 19 21 29 8 28 9 14 9 4 8 22 31 18 14 35
printing vector v2:
10 17 16 12 1 10 20 17 19 4 5 9 5 10 10 3 16 6 14 4 4 8 15 4 9 1 19 19 1 17 19 2 10 19 10 18 13 3 19 13 19 20 11 18 19 12 16 9 17 12 3 15 13 16 9 7 3 7 16 14 10 3 5 17 2 19 3 12 2 20 18 17 13 10 16 13 1 11 4 10 2 9 2 10 16 4 3 6 3 6 9 7 18 18 13 13 10 15 2 10
Searching element 10 linearly…in v1 :Found
printing vector v2 after sorting:
1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 6 6 6 7 7 7 8 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 11 11 12 12 12 12 13 13 13 13 13 13 13 14 14 15 15 15 16 16 16 16 16 16 16 17 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 19 19 19 19 20 20 20
Searching element 5 Binary search…in v2 :Found
Process exited normally.
Press any key to continue . . .
