Question #45932

you are to write and implement a C++ program to implement two search algorithms (linear search and binary search) on randomly generated integers stored in vectors.
• void Vectors ( vector < int >& v1, vector < int >& v2, int s1, int s2 ) : Fills the elements of vectors v1 and v2 with random numbers, generated by two sets of pseudo-random numbers with the seed values s1 and s2, where s1 is for v1and s2 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

Expert's answer

`#include <cstdlib>`

#include <vector>

#include <ctime>

#include <iomanip>

#include <iostream>

void Vectors( std::vector<int>& randomNumbers1, std::vector<int>& randomNumbers2, int start, int finish ) {

for ( int i = 0; i < 1000; i++ ) {

randomNumbers1.push_back((rand()%finish)+start);

}

for ( int i = 0; i < 1000; i++ ) {

randomNumbers2.push_back((rand()%finish)+start);

}

}

bool linearSearch (std::vector<int> &randomNumbers1, int x) {

for ( int i = 0; i < randomNumbers1.size(); i++ ) {

if ( randomNumbers1[i] == x ) {

return true;

}

}

return false;

}

bool binarySearch(std::vector<int> &randomNumbers1, int key, int imin, int imax) {

while (imin < imax) {

int imid = (imin+imax)/2;

if (randomNumbers1[imid] < key) {

imin = imid + 1;

} else {

imax = imid;

}

}

if ((imax == imin) && (randomNumbers1[imin] == key)) {

return true;

} else {

return false;

}

}

template <typename Type>

std::ostream& operator<<(std::ostream& out, const std::vector<Type>& lst) {

typename std::vector<Type>::const_iterator it = lst.begin();

out << "[ ";

for ( int i = lst.size() ; i > 1 ; it++, i-- ) {

out << "\'" << *it << "\'\n, ";

}

out << "\'" << *it << "\' ]";

return out;

}

int main() {

srand(time(NULL));

int randValue = rand()00;

std::vector<int> *randomNumbers1 = new std::vector<int>();

std::vector<int> *randomNumbers2 = new std::vector<int>();

Vectors(*randomNumbers1, *randomNumbers2, 1, 1000);

int anotherRandValue = rand()0;

//std::cout << *randomNumbers1 << std::endl;

std::cout << std::boolalpha << "Vector contains " << randValue << " equals " << linearSearch(*randomNumbers1, randValue) << std::endl;

std::cout << std::boolalpha << "Vector contains " << randValue << " equals " << binarySearch(*randomNumbers2, anotherRandValue, 0, randomNumbers1->size()) << std::endl;

}

## Comments

## Leave a comment