write and implement a C++ program to implement two search algorithms (linear search, binary search and print fuction) on randomly generated integers stored in vectors.

#include

const int DATA_RANGE = 100; const int DATA_SIZE = 100; const int DATA_SEED = 7; const int SEARCH_SEED = 9;

bool linear_search(const vector& inputVec, const int x, int& comparisons)

{ }

bool binary_search(const vector& inputVec, const int x, int& comparisons)

{ }

void print_vec( const vector& vec )

{ }

void average_comparisons(const vector& inputVec, const vector& searchVec, bool (*search)(const vector&, const int, int&) ) { int i, comparison=0, sum=0, found = 0; bool res; for (i=0; i<(int)searchVec.size(); i++) { res = search( inputVec, searchVec[i], comparison ); sum += comparison; if ( res ) found++; } cout << found << " numbers are found. The average number of comparisons in each search: " << (double)sum/(double)searchVec.size() << endl << endl; }

int random_number() { return rand()%DATA_RANGE+1; }

int main () {

// -------- create unique random numbers ------------------// vector inputVec(DATA_SIZE); srand(DATA_SEED); generate(inputVec.begin(), inputVec.end(), random_number); sort(inputVec.begin(), inputVec.end()); vector::iterator it = unique(inputVec.begin(), inputVec.end()); inputVec.resize( it - inputVec.begin() ); random_shuffle( inputVec.begin(), inputVec.end() );

cout << "------ Data source: " << inputVec.size() << " unique random numbers ------" << endl; print_vec(inputVec); cout << endl;

// -------- create random numbers to be searched ---------// vector searchVec(DATA_SIZE/2); srand(SEARCH_SEED); generate(searchVec.begin(), searchVec.end(), random_number);

cout << "------ " << searchVec.size() << " random numbers to be searched: ------" << endl; print_vec(searchVec); cout << endl;

cout << "Linear search: "; average_comparisons(inputVec, searchVec, linear_search); cout << "Binary search: "; average_comparisons(inputVec, searchVec, binary_search);

sort(inputVec.begin(), inputVec.end()); cout << "------- numbers in data source are now sorted ---------" << endl << endl; cout << "Linear search: "; average_comparisons(inputVec, searchVec, linear_search); cout << "Binary search: "; average_comparisons(inputVec, searchVec, binary_search);

return 0;

}