Question

In c++

A binary search member function of SortedType has the following prototype:
void.SortedType::BinarySearch(int value, bool& found);
Write the function definition as a recursive search, assuming an array-based implementation. Add a main function as a driver to test the BinarySearch. Test the edge cases.

Answer 1

#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[],int l,int r,int x)
{
if (r >= l)
{
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x); //If element is smaller than mid, then it can only be present in left //subarray
return binarySearch(arr, mid + 1, r, x); // Else the element can only be present in right subarray
}
return -1;
}
int main(void)
{
int n;
cout<<"Enter the number of elements-\n";
cin>>n; //reading n
int arr[n+1];
cout<<"Enter the array elements-\n";
for(int i=0;i<n;i++)
{
cin>>arr[i]; //reading array elements
}
int x;
cout<<"Enter the element to be found-\n";
cin>>x;
int result = binarySearch(arr, 0, n - 1, x); // calling function binarySearch
if(result==-1)
cout<<"Element not found";
else
cout<<"Element found at index - "<<result;
return 0;
}