Recursive Version Of The Binary Search

Introduction:

The objective of the program is to write a recursive version of the binary search. And write a program to test it.

Source: MindTap Computing for Malik's C++ Programming From Problem Analysis to Program Design, 8th Edition, [Instant Access] (8th)-Malik, chapter 16, programming exercises 19.

Solved!

Program Plan:

·       Define header section.

·       Define binSearch() fuction with parameter int arr[], int left, int right, int key.

o   If left become is greater than right return -1.

o   Declare and Find mid mid = (left + right) / 2.

o   If arr[mid] is key return mid index.

o   Else if arr[mid] > key return function call binSeach(arr, left, mid-1, key) for left array search.

o   Else return function call binSeach(arr, mid + 1, right, key) for righ array search.

·       Define main() function.

o   Declare n.

o   Ask user to input array size.

o   Use cin >> to take input.

o   Declare array arr of size n.

o   Take user input for array for arr.

o   Declare key.

o   Take user input for key.

o   Call to binSearch(arr, 0, n - 1, key) and declare p to store return value.

o   Print result.

Program:

// Object of program is to write recursive version of binary search.

#include <iostream>

using namespace std;

// binSeach() which take arr[], left, right and key as argument.
int binSeach(int arr[], int left, int right, int key)
{
    // if left become is greater than right.
    if (left > right)
    {
        // return -1 (not found)
        return -1;
    }

    // find mid.
    int mid = (left + right) / 2;
    // if arr[mid] is key.
    if (arr[mid] == key)
    {
        // return mid (found at mid index.)
        return mid;
    }
    // arr[mid] > key then
    else if (arr[mid] > key)
    {
        // search left half
        // return call binSeach(arr, left, mid-1, key)
        return binSeach(arr, left, mid - 1, key);
    }
    else
    {
        // search right half
        // return call binSeach(arr, mid+1, right, key)
        return binSeach(arr, mid + 1, right, key);
    }
}

// drive function.
int main()
{
    // declare n array size.
    int n;
    cout << "Enter array size:";
    // ask array size.
    cin >> n;

    // fill array.
    int arr[n];
    cout << "Enter " << n << " number of integers in sorted in ascending order:" << endl;
    // taking user input for each array cell.
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    // declare key.
    int key;
    cout << "Enter key integer you want to seach for in sorted array:";
    // take key to search.
    cin >> key;

    // call to binSeach() with argument arr, 0, n-1, key
    int p = binSeach(arr, 0, n - 1, key);
    // print result.
    if (p == -1)
    {
        cout << "Entered integer not found in array." << endl;
    }
    else
    {
        cout << "Entered integer found in array at index " << p << endl;
    }

    return 0;
}