Description
Purpose
The purpose of this lab is to demonstrate the speed difference between recursive and iterative binary search and sequential search. This difference is not shown if the array size is too small. Therefore, you should make your array as large as possible, and still have 2 significant digits of output. Binary search is much faster than sequential search.
Tasks
Create a Search Class
Member variables
- array of ints
- size of the array
- Whatever else you need
Constructor(int size) II initializes a Search Object with an internal integer array of the specified size
Destructor II destroys all data allocated by the constructor
bool SequentialSearch(int target) ” returns true if target is found in the object’s data array
bool RecursiveBinarySearch(int target) II returns true if target is found in the object’s data array (recursive)
bool RecursiveBinarySearchHelper(int lowlndex, int high Index, int target) IIcalied by RecursiveBinarySearchO
- bool IterativeBinarySearch(int target) ” returns true if target is found in the object’s data array void InitSortedArrayO
- Function to initialize the array with sorted random numbers
- call srand(O) before initializing to get the same numbers each time
- Don’t use a sortO function here. Rather, when initializing, insert a number a bit larger than the previous number.
- Array [0) = randt) %5
- Array[i+ 1) = Array[i) + randO %5 etc.
int *GetDataArrayO ” returns a pointer to the array of integers
Create a non-interactive driver that runs each of these searches and times and displays the outputs.
- Create a Search object specifying a large array size: say 1,000,000 – 10,000,000
Your timing results should be at least 2 significant digits
- to get at least 2 significant digits, you may have to display the output in micro or nano seconds (see timer section) Search for (using all three types of searches)
- a number at the beginning of the sorted array
- a number at the middle of the sorted array
- a number at the end of the sorted array
- a number NOT in the array (try -1)
Do not do any printing inside the searches.
- This will give you incorrect timer results.
Display the output to do each of the different searches
Sample Output
Creating a sorted array of 10000000
Finished creating a sorted array of 10000000
Searching for a number at the start of the array s.sequencialSearch() returned 1 in 364ns s.IterativeBinarySearch() returned 1 in 1459ns s.RecursiveBinarySearch() returned 1 in 1823ns
Searching for a number in the middle of the array s.sequencialSearch() returned 1 in 10187113ns s.IterativeBinarySearch() returned 1 in 1094ns s.RecursiveBinarySearch() returned 1 in 2188ns
Searching for a number at the end of the array s.sequencialSearch() returned 1 in 21273508ns s.IterativeBinarySearch() returned 1 ln 2188ns s.RecursiveBinarySearch() returned 1 in 3282ns
Searching for a number NOT in the array
s.sequencialSearch() returned 0 in 19723286ns s.IterativeBinarySearch() returned 0 ln 1458ns s.RecursiveBinarySearch() returned 0 in 3282ns
Random Numbers
Random Number generation in C/C++ is defined in the \<random\> header file.
Use void ‘srand(O)” to set the random number seed. The seed can be any value, but should be the same each time (so you can duplicate your results).
Use “int randt)” to generate a random number from 0 to MAXINT.
if you need a smaller random number when initializing the array, use randt) % 20 to get a random number between 0 and 19. Timer
Source code for a Timer class has been provided. You should include this class in your project to time things down to the nano-second
level. This class was written to be portable, however, I’ve not tried it in a non-Windows/non-zyBooks environment. If it does not work for
Mac or Linux. you may have to modify the source provided. All three environments should have a ‘high-resolution timer’. Example:
Timerti;
ti.StartO; II start the timer
II do something you want to time (don’t do any “cout’s” here. They take a long time ..)
usleep(521 000); II this should sleep for around 521 milliseconds ti.EndO; II end the timer
cout « “The timed event took” «ti.DurationlnNanoSecondsO « “ns” « endl;
cout « “The timed event took” «ti.DurationlnMicroSecondsO« “us” « endl;
cout « “The timed event took”« ti.DurationlnMiliiSecondsO « “ms” « end I;
You only need one Timer object for this project. You can “re-start’ him by calling ti.StartO again.
Modify these files
Main.cpp Search.cpp Search.h