we can do this by loop and recursion but here we will see how to solve the binary search problem by recursion.
Recursion is the function that calls itself multiple times directly or indirectly.
The condition for binary search is that the array must be sorted then only we can apply binary search.
here we are taking one example to find the key whether it is present or not.
#include<iostream>
using namespace std.
//creating recursive function.
bool binarysearch(int arr[], int s, int e, int k)
{
if(s>e)
{
return false;
}
int mid =s+(e-s)/2;
cout<<"value of mid is "<<arr[mid]<<endl;
//element found
if(arr[mid]==k)
{
return true;
}
if(arr[mid] < k)
{// mid+1 becomes starting point of the remaining array if k is greater than the mid then it is obvious that k is not present left of the mid index.
return binarysearch(arr,mid+1,e,k);
}
else
//here end is equal to mid-1
{
return binarysearch(arr,s,mid-1,k);
}
}
int main()
{
int arr[5] ={2,4,5,6,10};
int size = 5;
int key = 7;
bool ans = binarysearch(Arr,0,5,key);
if(ans)
{
cout<<"key is present";
}
else
{
cout<<"key is absent";
}
return 0;
}
//output
// key is absent
steps:
compare the mid index with the key
if it key=mid index then it returns true
if the mid index is smaller than the key then we have to recur to the right side as the key lie only to the right half subarray of the mid element and that is why start 's' becomes mid +1
if the mid index is greater than the key then we have to recur to the left side
and end 'e' becomes mid-1