Question

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

Answer 1

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