//PROGRAM CODE 9.4
// Function binary search (recursive)
#include<iostream.h>
#include<conio.h>

int Binary_Search(int A[],int low,int high,int key)
{
int mid;
if(low<=high) {
mid=(low+high)/2;
if(A[mid] == key)
{
//cout<<"\n\t Found";
return mid;
}
else if(key<A[mid])
return Binary_Search(A,low,mid-1, key);
else
return Binary_Search(A,mid+1,high, key);
}
return -1;
}
void main()
{

int i, size,A[20],ans,key;
clrscr();
cout<<"Enter array size = ";
cin>>size;

cout<<"\n Enter array elements";
for (i=0;i<size;i++)
{
cin>>A[i];
}
cout<<"Enter the element to be search =";
cin>>key;
ans = Binary_Search(A,0,size,key);
if(ans==-1)
	cout<<"\n Not found";
else
	cout<<"Found";

getch();
}

/*********************OUTPUT *******************************
Enter array size = 5

 Enter array elements
1 2 3 4 5

	 Enter the element to be search = 5

Found

Enter array size = 5

 Enter array elements
1 2 3 4 5

	 Enter the element to be search = 25

Not Found

***********************************************************/