You are to implement two search algorithms (linear search and binary search) in C++ on randomly generated integers stored in vectors. In this assignment, you will use routines from STL to implement these algorithms.

void genRndNums ( vector < int >& v, int seed ) : This routine generates random integers in the range [ LOW = 1, HIGH = 100 ] and puts them in vector v. Initializes the random number generator (RNG) by calling the function srand() with the seed value seed, and generates random integers by calling the function rand(). To use srand and rand, you need the header . The vector v is already allocated with space. Use vectors member function to get the size of the vector.

bool linearSearch ( const vector < int >& inputVec, int x ) : A linear search algorithm, where x is the searched item in vector inputVec. 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 from the STL .

bool binarySearch ( const vector < int >& inputVec, int x ) : A binary search algorithm, where x is the searched item in vector inputVec. If the search is successful, it returns true; otherwise, it returns false. To implement this routine, simply call the binary_search() function from the STL .

int search ( const vector < int >& inputVec, const vector < int >& searchVec, 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 searchVec in vector inputVec. 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 >& inputVec ) : A sort algorithm to sort the elements of vector inputVec in ascending order. To STL algorithms 2 implement this routine, simply call the sort() function from the STL .

void printStat ( int totalSucCnt, int vec_size ) : Prints the percent of successful searches as floating-point numbers on stdout, where totalSucCnt is the total number of successful comparisons and vec_size is the size of the test vector.

void print_vec ( const vector < int >& vec ): This routine displays the contents of vector vec on standard output, printing exactly NO_ITEMS = 10 numbers 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 = 6 spaces on standard output. You can re-use the implementation of this routine from Assignment 1, but remember to change the values of related constants.

Execute the srand ( ) function only once before generating the first random integer with the given seed value SEED. The rand ( ) function generates a random integer in the range [ 0, RAND_MAX ], where the constant value RAND_MAX is the largest random integer returned by the rand ( ) function and its value is system dependent. To normalize the return value to a value in the range [ LOW, HIGH ], execute: rand ( ) % ( HIGH LOW + 1 ) + LOW.

Here is the .cc file:

#include #include #include #include #include using namespace std;

const int DATA_SIZE = 100; const int SEARCH_SIZE = 50; const int DATA_SEED = 11; const int SEARCH_SEED = 7;

void genRndNums( vector& v, int seed ) { }

bool linearSearch( const vector& inputVec, int x) { }

bool binarySearch( const vector& inputVec, int x) { }

int search( const vector& inputVec, const vector& searchVec, bool (*p)( const vector&, int) ){ }

void sortVector (vector& inputVec) { }

void printStat (int totalSucCnt, int vec_size) { }

void print_vec( const vector& vec ){ }

int main() { vector inputVec(DATA_SIZE); vector searchVec(SEARCH_SIZE); genRndNums(inputVec, DATA_SEED); genRndNums(searchVec, SEARCH_SEED);

cout << "----- Data source: " << inputVec.size() << " randomly generated numbers ------" << en\ dl; print_vec( inputVec ); cout << "----- " << searchVec.size() << " random numbers to be searched -------" << endl; print_vec( searchVec );

cout << " Conducting linear search on unsorted data source ..." << endl; int linear_search_count = search( inputVec, searchVec, linearSearch ); printStat ( linear_search_count, SEARCH_SIZE );

cout << " Conducting binary search on unsorted data source ..." << endl; int binary_search_count = search( inputVec, searchVec, binarySearch ); printStat ( binary_search_count, SEARCH_SIZE );

sortVector( inputVec );

cout << " Conducting linear search on sorted data source ..." << endl; linear_search_count = search( inputVec, searchVec, linearSearch ); printStat ( linear_search_count, SEARCH_SIZE );

cout << " Conducting binary search on sorted data source ..." << endl; binary_search_count = search( inputVec, searchVec, binarySearch ); printStat ( binary_search_count, SEARCH_SIZE );

return 0; }