Question

The binary search algorithm given in this chapter is nonrecursive. Write and implement a recursive version of the binary search algorithm.

The program should prompt Y / y to continue searching and N / n to discontinue. If an item is found in the list display the following message:

 x found at position y

else:

x is not in the list

Use the following list of integers when testing your program: 2, 6, 8, 13, 25, 33, 39, 42, 53, 58, 61, 68, 71, 84, 97

*Need the answer in C++*

Answer 1

Ans

code:-

#include <iostream>

using namespace std;

int bsearch(int arr[],int l,int r,int item){

if(r>=l){

int mid=l+(r-l)/2;//find mid

//if found return mid

if(arr[mid]==item) return mid;

//else call recursive

if(arr[mid]>item)

return bsearch(arr,l,mid-1,item);

return bsearch(arr,mid+1,r,item);

}

return -1;

}//for testing

int main()

{

char ch='Y';

int item;

//array

int a[]={2,6,8,13,25,33,39,42,53,58,61,68,71,84,97};

while(ch=='Y'||ch=='y'){//input item

cout<<"Enter item to search"<<endl;

cin>>item; //call search function

int res= bsearch(a,0,14,item);

if(res==-1)

cout<<item<<" not in the list"<<endl;

else//print the index number

cout<<item<<" found at position "<<res<<endl;

cout<<"Do you want to continue y or n"<<endl;//do you continue

cin>>ch;

}

return 0;

}

If any doubt ask in the comments.