If you want to find the presence of a element in a given sorted range, then you can use the binary_search function defined in the STL algorithm.
The range should be sorted in ascending order to perform binary search.
It returns true if element is found within the range, else returns false.
Template for the function binary_search
bool binary_search (RandomIterator first, RandomIterator last, const T& val);
About parameters
first
RandomIterator for the initial position of the range which is included in the range.
last
RandomIterator for the final position which it not included in the range.
val
value to be searched within the range.
A sample program using binary_serach
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector <int> v;
v = {48,9,2,7,83,6,6,67,5};
//printing the elements in the range
cout << "Before Sorting : ";
for ( int i: v) cout << i << " ";
cout << endl;
//applying sort function in the range
sort(v.begin(),v.end());
//printing the elements in the range
cout << "After Sorting : ";
for ( int i: v) cout << i << " ";
cout << endl;
//binary search for 7
if (binary_search(v.begin(),v.end(),7)) {
cout << "7 found in the range" << endl;
} else {
cout << "7 not found in the range" << endl;
}
//binary search for 3
if (binary_search(v.begin(),v.end(),3)) {
cout << "3 found in the range" << endl;
} else {
cout << "3 not found in the range" << endl;
}
return 0;
}
Use C++11 mode ( if you want to use range-based for loops)
Output of the above program
Before Sorting : 48 9 2 7 83 6 6 67 5
After Sorting : 2 5 6 6 7 9 48 67 83
7 found in the range
3 not found in the range
Time complexity for binary search is logarithmic in between the range.
0 Comment(s)