Suppose a one-dimensional array AR containing integers is arranged in ascending order. Write a user-defined function in C++ to search for an integer from AR with the help of Binary search method, returning an integer 0 to show absence of the number and integer 1 to show presence of the number in the array. Function should have three parameters : (i) array AR (ii) the number to be searched and (iii) the number of elements N in the array.
Source Code
#include<iostream>
using namespace std;
bool bsearch(int AR[], int N, int VAL);
int main()
{
int AR[100],n,val;
bool found;
cout<<"Enter number of elements you want to insert ";
cin>>n;
cout<<"Enter element in ascending order\n";
for(int i=0;i<n;i++)
{
cout<<"Enter element "<<i+1<<":";
cin>>AR[i];
}
cout<<"\nEnter the number you want to search ";
cin>>val;
found=bsearch(AR,n,val);
if(found)
cout<<"\nItem found";
else
cout<<"\nItem not found";
return 0;
}
bool bsearch(int AR[], int N, int VAL)
{
int Mid,Lbound=0,Ubound=N-1;
while(Lbound<=Ubound)
{
Mid=(Lbound+Ubound)/2;
if(VAL>AR[Mid])
Lbound=Mid+1;
else if(VAL<AR[Mid])
Ubound=Mid-1;
else
return true;
}
return false;
}
Output
SAMPLE RUN # 1
Enter number of elements you want to insert 5
Enter element in ascending order
Enter element 1: 13
Enter element 2: 19
Enter element 3: 23
Enter element 4: 50
Enter element 5: 67
Enter the number you want to search 23
Item found
SAMPLE RUN # 2
Enter number of elements you want to insert 3
Enter element in ascending order
Enter element 1: 33
Enter element 2: 59
Enter element 3: 63
Enter the number you want to search 30
Item not found