Algorithm:

Binary search actually divides the entire array into two halves at each iteration and do the search in one half based on the searching element since the array is sorted.

Let,

• Starting index=0
• End index=n-1, where n is the array length
• Middle index= (start + end index)/2= (n-1)/2, this middle index divides the array into two half
• If array[middle]==search value
• We are done
• Else if array [middle] < search value
• Then we need to search in the upper half
• Else if array [middle]>search value
• Then we need to search in the lower half
• These three cases need to be handled recursively to implement a binary search.
• Clearly, these searching method is possible due to the sorted input array.

Function definition:

We can build up a recursive binSearch()function which will do the binary search.

Function binSearch(input array,start index, end index,search value)
    middle index=(start index + end index)/2;    
    //if search value found return position(1-indexed position)
    IF array[middle index] == search value
        return middle index+1;
    //if search value>array[middle index], search in the segment 
    //(middle index+1,end index), i.e., the upper half & 
    //search until start index==end index 
    ELSE IF (search value>array[middle index] &start index!= end index)
        return binSearch(input array,middle index+1,end index,search value);//recursive call
    //if search value<array [middle index] search in the segment 
    //(start index, middle index-1), i.e., the lower half& search until start index== end index
    ELSE IF(search value<array[middle index] &start index!= end index)
        return binSearch(input array, start index,middle index-1,seach value);
    //search value not found as start index == end index
    ELSE
    return 0;
END Function

Example & Explanation:

    Let the input array be:
    2 5 8 9 12 13 16, length, n=7
    Search element: 5

    //In main function:
    
    Make call binSearch(array, 0,7,5)
    binSearch (array, 0, 7, 5)
    middle index =(0+7)/2=3
    array[3]!=5
    array[3]>5&& 0<7
    
    make callbinSearch(array, 0, 3-1)
    binSearch(array, 0, 3-1)
    middle index =(0+2)/2=1
    array[1]==5
    return (1+1) //position 2
    
    Program terminated

C++ implementation for binary search on sorted array

#include <stdio.h>
#include <stdlib.h>

//binary search implementation using recursion
int binSearch(int* a,int first,int last,int t){
	//find middle index
	int mid=(first+last)/2;
	//if data found return position(1-indexed position)
	if(a[mid]==t)
		return mid+1;
	//if data > a[mid] search in the segment (mid+1,last)
	else if(t>a[mid] & first!=last)//search until first!=last
		return binSearch(a,mid+1,last,t);
	//if data < a[mid] search in the segment (first,mid-1)
	else if(t<a[mid] & first!=last)
		return binSearch(a,first,mid-1,t);
	else
		return 0;
}

int main()
{   
	int n,t;
	printf("enter number of array elements: ");
	scanf("%d",&n);

	int* a=(int*)(malloc(sizeof(int)*n));

	printf("enter elements: \n");
	//input array elements
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);

	printf("enter element to search\n");
	scanf("%d",&t);
	//output result
	if(binSearch(a,0,n-1,t))
		printf("\n%d found at position %d\n",t,binSearch(a,0,n-1,t));
	else
		printf("\n%d not found\n",t);

	return 0;
}

Output (first run)

enter number of array elements: 7
enter elements:
2 5 8 9 12 13 16
enter element to search
5

5 found at position 2

Output (second run)

enter number of array elements: 6
enter elements:
11 34 45 56 67 78
enter element to search
20

20 not found