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)