C++ Algorithm binary_search function is used check whether the element in the range [first, last) is equivalent to val (or a binary predicate) and false otherwise.
- The range [first, last) must satisfy all of the following conditions: Partitioned with respect to element < val or comp (element, val). Partitioned with respect to !(val < element) or !comp(value, element) For all elements, if element < val or comp (element, val) is true then !(val < element) or !comp(val, element) is also true.
- The first version uses operator< to compare the elements and the second version uses the given comparison function i.e. comp.
- Partitioned with respect to element < val or comp (element, val).
- Partitioned with respect to !(val < element) or !comp(value, element)
- For all elements, if element < val or comp (element, val) is true then !(val < element) or !comp(val, element) is also true.
Syntax
default (1) template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last,
const T& val);
custom (2) template <class ForwardIterator, class T, class Compare>
bool binary_search (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
Parameter
A forward iterator that references the initial element within the range intended for searching.
last: A forward iterator indicating the element after the last one in the range being examined.
A custom binary predicate function named comp is implemented to evaluate two arguments and determine if they are in the correct sequence. By adhering to the strict weak ordering principle, this function is able to sort elements effectively.
val: A value representing the maximum limit for comparing the elements within the specified range.
Return value
It returns true when a matching element to the value is discovered, otherwise, it returns false.
Complexity
On average, the complexity grows logarithmically with the separation between the initial and final elements, executing a maximum of log base 2 of N plus 2 comparisons, where N equals the difference between the last and first elements.
Data races
The items within the range [first, last) are being retrieved.
Exceptions
This function will raise an exception if an error occurs during either comparing elements or performing an operation on an iterator.
Please be aware that using incorrect parameters can lead to unpredictable behavior.
Example 1
Let's examine a straightforward example to showcase the utilization of the binary_search function:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {3, 1, 4, 6, 5};
if (binary_search(v.begin(), v.end(), 4)) {
cout << "4 found" << endl;
}
else {
cout << "4 not found" << endl;
}
return 0;
}
Output:
4 found
Example 2
Let's see another simple example:
#include <iostream> // std::cout
#include <algorithm> // std::binary_search, std::sort
#include <vector> // std::vector
using namespace std;
bool myfunction (int i,int j) { return (i<j); }
int main () {
int myints[] = {1,2,3,4,5,4,3,2,1};
vector<int> v(myints,myints+9); // 1 2 3 4 5 4 3 2 1
// using default comparison:
sort (v.begin(), v.end());
cout << "looking for a 3... ";
if (binary_search (v.begin(), v.end(), 3))
cout << "found!\n"; else cout << "not found.\n";
// using myfunction as comp:
sort (v.begin(), v.end(), myfunction);
cout << "looking for a 6... ";
if (binary_search (v.begin(), v.end(), 6, myfunction))
cout << "found!\n"; else std::cout << "not found.\n";
return 0;
}
Output:
looking for a 3... found!
looking for a 6... not found.
Example 3
Let's examine another straightforward example to contrast the elements using a comparison function:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 9, 10};
vector<int> v(a, a+9);
cout <<"\nHere are the values in the vector:\n";
for (vector<int>::size_type i=0; i<v.size(); i++)
cout <<v.at(i)<<" ";
if (binary_search(v.begin(), v.end(), 3))
cout <<"\nThe value 3 was found.";
else
cout <<"\nThe value 3 was not found.";
if (binary_search(v.begin(), v.end(), 8))
cout <<"\nThe value 8 was found.";
else
cout <<"\nThe value 8 was not found.";
return 0;
}
Output:
Here are the values in the vector:
1 2 3 4 5 6 7 9 10
The value 3 was found.
The value 8 was not found.
Example 4
Let's see another simple example:
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iomanip>
using namespace std;
void print(vector <int> vs)
{
vector <int>::iterator i;
for(i = vs.begin(); i != vs.end(); i++)
{
cout << left << setw(2) << *i;
}
cout << endl;
}
int main () {
int arr[] = {1, 5, 2, 9, 8, 4, 3, 7, 6};
int alen = sizeof(arr) / sizeof(int);
vector <int> v(arr, arr + alen);
sort (v.begin(), v.end());
cout << "Sorted vector elements : ";
print(v);
// Searching without using predicate
cout << "Searching for 4 : ";
if (binary_search (v.begin(), v.end(), 4))
cout << "found!" << endl;
else
cout << "not found." << endl;
// Searching using predicate
cout << "Searching for element greater than 9 : ";
if (binary_search(v.begin(), v.end(), 9, greater<int>()))
cout << "found!" << endl;
else
cout << "not found." << endl;
return 0;
}
Output:
Sorted vector elements : 1 2 3 4 5 6 7 8 9
Searching for 4 : found!
Searching for element greater than 9 : not found.
