Part 1: Compare Search Algorithms
Write a program to find the number of comparisons using the binary search and sequential search algorithms as follows:
Start with an empty vector. Start by create two search functions over a vector:
int sequencialSearch(int n, vector<int> nums, int &compares)– Do a sequential search for n, return index if found, otherwise -1.compareswith be incremented each time a comparison is made.int binarySearch(int n, vector<int> nums int &compares)– Do a binary search for n, return index if found, otherwise -1.compareswill be incremented each time a comparison is made.
These
Then write the following test program:
a. Use a random number generator to fill the vector A with 10,000 random numbers between 1 and 1,000,000.
b. Sort the list.
c. Likewise create a second vector B of 1,000 numbers. The first 500 should be randomly selected from elements A, and the others completely random numbers between 1 and 1,000,000.
d. For each number in vector B look up that number in vector A using both the sequencialSearch search and the binarySearch search. Use the count parameter to keep track of the number of comparisons done for each search.
e. Sum up all the compares for each algorithm. Display the results.