# Binary Search (Recursive)

## Program Listing

• This program performs a binary search on a sorted list.
• There are two BinarySearch() functions: one is recursive; one is nonrecursive.
• The first call is to the nonrecursive binary search function. It sets the initial endpoints on the sublist to be searched.
• The subsequent calls (by the second binary search function) are recursive. Each one sets the endpoints of a sublist half as long as the previous sublist.

### RecursiveBinSearch.cpp

 ```/************************************************************************ * * * Program: RecursiveBinSearch.cpp * * * * Abstract: This program will perform a binary search of a list * * for a specified value * * * ************************************************************************/ // Header files #include #include #include using namespace std; // Function prototypes int BinarySearch(int array[], int size, int value); int BinarySearch(int array[], int left, int right, int value); void Sort(int array[], int size); /************************************************************************ * * * Function: main * * * * Purpose: To perform a binary search of a list for a specified * * value * * * ************************************************************************/ int main() { const int sentinel = -1; const int maxSize = 100; int array[maxSize]; int size = maxSize; // Create an array of random integers for (int i = 0; i < size; i++) array[i] = rand() % 1000; // Sort and print the array Sort(array, size); for (int i = 0; i < size; i++) cout << array[i] << ' '; cout << endl << endl; // Search the array for values given by the user cout << "Enter a number to be search for (enter " << sentinel << " to quit): " << flush; int value; cin >> value; while (value != sentinel) { // Search the array int pos = BinarySearch(array, size, value); // Report the results if (pos >= 0) cout << value << " was found in position " << pos << endl; else cout << value << " was not found" << endl; cout << "Enter a number to be search for (enter " << sentinel << " to quit): " << flush; cin >> value; } cout << endl << "Good-bye" << endl; return 0; } /************************************************************************ * * * Function: BinarySearch(int[], int, int) * * * * Purpose: To perform a binary search of a list for a specified * * value * * * ************************************************************************/ int BinarySearch(int array[], int size, int value) { // Set the sublist endpoints and call on the recursive binary search return BinarySearch(array, 0, size - 1, value); } /************************************************************************ * * * Function: BinarySearch(int[], int, int, int) * * * * Purpose: To perform a binary search of a list for a specified * * value * * * ************************************************************************/ int BinarySearch(int array[], int left, int right, int value) { // If there is a sublist to search, search it if (left <= right) { int middle = (left + right)/2; // If value is in first half, search first half if (value < array[middle]) return BinarySearch(array, left, middle - 1, value); // If value is in second half, search second half else if (value > array[middle]) return BinarySearch(array, middle + 1, right, value); // Otherwise, value was found else return middle; } // If there is no sublist to search, report that value was not found else return -1; } /************************************************************************ * * * Function: Sort * * * * Purpose: To sort a list of integers into ascending order * * * ************************************************************************/ void Sort(int array[], int size) { // Use the quick-and-dirty bubble sort for (int i = 0; i < size - 1; i++) for (int j = 0; j < size - 1 - i; j++) if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } return; }```

### Sample Run

 ```5 10 22 31 51 54 60 61 67 71 84 85 86 88 89 96 102 113 116 134 137 139 143 145 160 165 181 183 188 201 212 225 233 248 259 262 306 311 318 327 336 343 353 367 394 403 406 414 419 422 444 457 475 479 495 505 514 515 516 521 524 536 543 561 562 566 606 627 628 629 644 653 670 693 729 736 738 749 751 754 757 758 760 767 803 825 834 838 851 882 894 920 945 962 966 967 978 979 983 990 Enter a number to be search for (enter -1 to quit): 212 212 was found in position 30 Enter a number to be search for (enter -1 to quit): 5 5 was found in position 0 Enter a number to be search for (enter -1 to quit): 990 990 was found in position 99 Enter a number to be search for (enter -1 to quit): 3 3 was not found Enter a number to be search for (enter -1 to quit): 999 999 was not found Enter a number to be search for (enter -1 to quit): 500 500 was not found Enter a number to be search for (enter -1 to quit): -1 Good-bye ```