Recursive Binary Search

Binary Search is a search algorithm that is used to find the position of an element (target value ) in a sorted array. The array should be sorted prior to applying a binary search. Binary search is also known by these names, logarithmic search, binary chop, half interval search.

Algorithm

The binary search algorithm works by comparing the element to be searched by the middle element of the array and based on this comparison follows the required procedure.

Case 1 - element = middle, the element is found return the index.
Case 2 - element > middle, search for the element in the sub-array starting from middle+1 index to n.
Case 3 - element < middle, search for element in the sub-array starting from 0 index to middle -1.

The implementation of the binary search algorithm function uses the call to function again and again.
This call can be of two types −

Iterative
Recursive

Recursive call is calling the same function again and again. The recursive method follows the divide and conquers approach. The recursive solution utilizes a helper function to keep track of pointers to the section of the list we are currently examining. The search either completes when we find the key, or the two pointers meet.

Here we are going to implement binary search using the recursive method.

Program using C

// RECURSIVE BINARY SEARCH
#include<stdio.h>
#include<stdlib.h>
int RecursiveBinary(int[], int, int, int);
int main()
    {
        int A[50], n, el, i, pos;
        printf("Enter the no. of elements: ");
        scanf("%d",&n);
        printf("Enter the sorted array elements(ASC):- ");
        for(i=0;i<n;i++)
            scanf("%d",&A[i]);
        printf("Enter the element to be searched:- ");
        scanf("%d",&el);
        pos = RecursiveBinary(A,0,n-1,el);
        if(pos == -1)
            printf("Element not found\n");
        else
            printf("Element found in %d index.",pos);
        return 0;
    }
    
    
    int RecursiveBinary(int A[], int beg, int end, int el)
    {
        int mid;
        if(beg>end)
            return(-1);
        else
            {
                mid = (beg + end)/2;
                if(el == A[mid])
                    return (mid);
                else
                {
                    if(el > A[mid])
                        RecursiveBinary(A,mid+1,end,el);
                    else
                        RecursiveBinary(A,beg,mid-1,el);
                }
            }	
    }