CPP Binary Search Using Recursion Program Example

    1. Home
    2. Tutorials
    3. CPP
    4. CPP Programs
    5. Recursion
    6. Program

    Source Code:

    #include <iostream>
    using namespace std;

    // function name BS means binary search
    int BS(int arr[], int left, int right, int num)
    {
        //base condition for recursion
        if (right >= left) {
            /* calculating mid of array to 
            divide it into two parts */

            int mid = left + (right - left) / 2;

            // If the element found at the mid
            if (arr[mid] == num)
                return mid; // returning mid index

            /* if element is smaller then we have to
                find it in left subarray */

            if (arr[mid] > num)
                return BS(arr, left, mid - left, num);

            /* if element is smaller then we have to
                find it in left subarray */

            return BS(arr, mid + left, right, num);
        }
        // -1 indicate value not found
        return -1;
    }

    int main(void)
    {
        // initialization of array having 10 elements
        int arr[] = { 45, 12, 22, 19, 88, 54, 66, 12, 40, 77 };
        int num; // variable to get input of number to search
        cout<<"Enter Number to Search: ";
        cin>>num;
        // using sizeof operator to calculate elements of array
        int n = sizeof(arr) / sizeof(arr[0]);
        n = n-1; // because last index always = total elements - 1
        int res = BS(arr, 0, n, num);
        if(res == -1) {
            cout << "Element is not Found"<<endl;
        } else {
            cout << "Element Found at index " << res;
        }
        return 0;
    }

    Output:

    binary search program and algorithm using c++

    Working:

    Binary search algorithm is implemented using recursion, because this algorithm involves continous divion of provided data set into two halves. Word binary means two. So that the algorithm get the mid of the input array and check whether the mid element is equal to the provided search key, if not then algorithm find it in the subsequent parts of the array. 

    This algorithm involve the following procedure recursively.

    1. Sort Array (Learn about Sorting Techniques)
    2. Divide array into two halves
    3. Match search key with value at mid index
    4. If value match with mid index value then return index
    5. Else if search key is greater then mid value the skip the lower half
    6. Else if search key is smaller then mid value the skip the upper half
    7. Repeat from step 2

    Here base condition for this recursive algorithm is right > left. This means that array can further be divided into two halves. An when this condition will false then array cannot further divided so that recursion will terminate. In case of value match this algorithm will return its index. Otherwise unsuccessfull completion algorithm will return -1.

    In main function we have initialized an array of 10 distinct elements. A variable of int type is declared to input serach key from user. After declaration process input is taken from the user using cout and cin objects. BS (binary Search) algorithm is called providing array and search key.

    Finally we check if the return value of BS algorithm if it is -1 then we are displaying message "Element is not Found" other wise we will print the message including the index at which we found value.

    Comments
    Login to TRACK of Comments.