Coders Packet

Binary Search Using STL in C++

By AMAN KUMAR PANDEY

Binary Search in C++ using binary search function present in STL(Standard Template Library).

 

In the Binary Search algorithm, the entered array should be in ascending order.

My program is designed in such a way, that the code asks the user to input the array in ascending order(as it is a necessary condition for binary search). Now we can call the function "Binary_Search()" present in STL to check whether the entered element is present or not. If the entered element is present in the array, then we will find the upper bound of the searched element in the array using the "upper_bound()" function, which will return the pointer pointing to the next element of a searched element. Now we can subtract the base address of the array with the returned value of the upper bound function which will give our location of a searched element in the array.
If the above condition does not satisfy, then it will display "ELEMENT NOT FOUND".
According to my Code-->
Assume an array "a" of size "n" with the element to be searched "k".
In this program, I have used the Binary Search function which is present in STL(Standard Template Library)of C++.
The time complexity of the algorithm is O(log n).

 

 

CODE-->

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cout<<"\n ENTER THE SIZE OF ARRAY -> ";

int a[10000];
cin>>n;
cout<<"\n ENTER THE ARRAY IN ASCENDING ORDER -> ";

for(int i=0;i<n;i++)
{
cin>>a[i];

}
cout<<"\n ENTER THE ELEMENT TO BE SEARCHED -> ";
int k;
cin>>k;
if(binary_search(a,a+n,k))
{
auto s=upper_bound(a,a+n,k);
cout<<"-------------------------------------------------";
cout<<"\n ELEMENT FOUND AT POSITION -> "<<s-a<<endl;
cout<<"-------------------------------------------------";
}

else
{ cout<<"-----------------------------------";
cout<<"\n ELEMENT NOT FOUND ";
cout<<endl;
cout<<"-----------------------------------";
}
return 0;
}


 

Input- ENTER THE SIZE OF ARRAY -> 6

           ENTER THE ARRAY IN ASCENDING ORDER -> 1 2 3 4 8 9

           ENTER THE ELEMENT TO BE SEARCHED -> 8

 

 

Output-   ----------------------------------------
               ELEMENT FOUND AT POSITION -> 5
               ----------------------------------------


Input- ENTER THE SIZE OF ARRAY -> 8

           ENTER THE ARRAY IN ASCENDING ORDER -> 1 2 3 4 6 7 8 9

           ENTER THE ELEMENT TO BE SEARCHED -> 5

 

 

Output-   ----------------------------------------
                ELEMENT NOT FOUND
               ----------------------------------------

Download project

Reviews Report

Submitted by AMAN KUMAR PANDEY (amanpandey)

Download packets of source code on Coders Packet