Description

5/5 - (2 votes)

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