|
binary_search
function template
<algorithm>
template <class ForwardIterator, class T>
bool binary_search ( ForwardIterator first, ForwardIterator last,
const T& value );
template <class ForwardIterator, class T, class Compare>
bool binary_search ( ForwardIterator first, ForwardIterator last,
const T& value, Compare comp );
Test if value exists in sorted array
Returns true if an element in the range [first,last) is equivalent to value, and false otherwise.
The comparison is performed using either operator< for the first version, or comp for the second: A value, a, is considered equivalent to another, b, when (!(a<b) && !(b<a)) or (!comp(a,b) && !comp(b,a))
For the function to yield the expected result, the elements in the range shall already be ordered according to the same criterion (operator< or comp).
The behavior of this function template is equivalent to:
1
2
3
4
5
6
|
template <class ForwardIterator, class T>
bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value )
{
first = lower_bound(first,last,value);
return (first!=last && !(value<*first));
}
|
Parameters
- first, last
- Forward iterators to the initial and final positions of the sequence to be searched. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
- value
- Element value to search for.
- comp
- Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.
Return value
true if an element in value is found, and false otherwise.
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
// binary_search example
#include <iostream>
#include <algorithm>
#include <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 cout << "not found.\n";
return 0;
}
|
Output:
looking for a 3... found!
looking for a 6... not found.
|
Complexity
At most, logarithmic number of comparisons and linear number of steps in the length of [first,last) +2.
If used with random-access iterators, number of steps is reduced to logarithmic.
See also
| find | Find value in range (function template) |
| lower_bound | Return iterator to lower bound (function template) |
| upper_bound | Return iterator to upper bound (function template) |
| equal_range | Get subrange of equal elements (function template) |
|