Search Project #4 Solution

$35.00

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