(Recursive Binary Search) Modify Fig. 19.3 to use recursive function recursiveBinary- Search to perform a binary search of the vector. The function should receive the search key, starting index and ending index as arguments. If the search key is found, return its index in the vector. If the search key is not found, return –1.

Question

What will be an ideal response?

Answer 1

```
// Class that contains a vector of random integers and a recursive
// binary search function that finds an integer.
#include
using namespace std;

class BinarySearch
{
public:
BinarySearch( int ); // constructor initializes vector
int binarySearch( int ) const; // perform binary search on the vector
void displayElements() const; // display vector elements
private:
int size; // vector size
vector< int > data; // vector of ints
void displaySubElements( int, int ) const; // display range of values

// perform recursive binary search on the vector
int recursiveBinarySearch( int, int, int ) const;
}; // end class BinarySearch
```
```
// BinarySearch class member-function definition.
#include
#include // prototypes for functions srand and rand
#include // prototype for function time
#include // prototype for sort function
#include "BinarySearch.h" // class BinarySearch definition
using namespace std;

// constructor initializes vector with random ints and sorts the vector
BinarySearch::BinarySearch( int vectorSize )
{
size = ( vectorSize > 0 ? vectorSize : 10 ); // validate vectorSize
srand( time( 0 ) ); // seed using current time

// fill vector with random ints in range 10-99
for ( int i = 0; i < size; i++ )
data.push_back( 10 + rand() % 90 ); // 10-99

std::sort( data.begin(), data.end() ); // sort the data
} // end BinarySearch constructor

// perform a binary search on the data
int BinarySearch::binarySearch( int searchElement ) const
{
int low = 0; // low end of the search area
int high = size - 1; // high end of the search area

return recursiveBinarySearch( searchElement, low, high );
} // end function binarySearch

// perform a recursive binary search on the data
int BinarySearch::recursiveBinarySearch(
int searchElement, int low, int high ) const
{
if ( low > high ) // test base case; no element left to check
return -1;

// print remaining elements of vector to be searched
displaySubElements( low, high );

int middle = ( low + high + 1 ) / 2; // middle element

// output spaces for alignment
for ( int i = 0; i < middle; i++ )
cout << " ";

cout << " * " << endl; // indicate current middle

int location = -1; // variable to return; -1 if the value was not found

// if the element is found at the middle
if ( searchElement == data[ middle ] )
location = middle; // location is the current middle
else if ( searchElement < data[ middle ] ) // middle is too high
// eliminate the higher half
location = recursiveBinarySearch( searchElement, low, middle - 1 );
else // middle element is too low
// eliminate the lower half
location = recursiveBinarySearch( searchElement, middle + 1, high );

return location; // return location of search key
} // end function recursiveBinarySearch

// display values in vector
void BinarySearch::displayElements() const
{
displaySubElements( 0, size - 1 );
} // end function displayElements

// display certain values in vector
void BinarySearch::displaySubElements( int low, int high ) const
{
for ( int i = 0; i < low; i++ ) // output spaces for alignment
cout << " ";

for ( int i = low; i <= high; i++ ) // output elements left in vector
cout << data[ i ] << " ";

cout << endl;
} // end function displaySubElements
```
```
// BinarySearch test program.
#include
#include "BinarySearch.h" // class BinarySearch definition
using namespace std;

int main()
{
int searchInt; // search key
int position; // location of search key in vector

// create vector and output it
BinarySearch searchVector( 15 );
searchVector.displayElements();

// get input from user
cout << "\nPlease enter an integer value (-1 to quit): ";
cin >> searchInt; // read an int from user
cout << endl;

// repeatedly input an integer; -1 terminates the program
while ( searchInt != -1 )
{
// use binary search to try to find integer
position = searchVector.binarySearch( searchInt );

// return value of -1 indicates integer was not found
if ( position == -1 )
cout << "The integer " << searchInt << " was not found.\n";
else
cout << "The integer " << searchInt
<< " was found in position " << position << ".\n";

// get input from user
cout << "\n\nPlease enter an integer value (-1 to quit): ";
cin >> searchInt; // read an int from user
cout << endl;
} // end while

return 0;
} // end main
```