binary_search(3C++) - binary_search(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMEbinary_search
- Performs a binary search for a value on a container.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator, class T>
boolbinary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template <class ForwardIterator, class T, class Compare>
boolbinary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
DESCRIPTION
The binary_search algorithm, like other related algorithms
(equal_range, lower_bound and upper_bound) performs a binary search on
ordered containers. All binary search algorithms have two versions. The
first version uses the less than operator (operator<) to perform the
comparison, and assumes that the sequence has been sorted using that
operator. The second version allows you to include a function object of
type Compare, which it assumes was the function used to sort the
sequence. The function object must be a binary predicate.
The binary_search algorithm returns true if a sequence contains an ele‐
ment equivalent to the argument value. The first version of
binary_search returns true if the sequence contains at least one ele‐
ment that is equal to the search value. The second version of the
binary_search algorithm returns true if the sequence contains at least
one element that satisfies the conditions of the comparison function.
Formally, binary_search returns true if there is an iterator i in the
range [first, last) that satisfies the corresponding conditions:
!(*i < value) && !(value < *i)
or
comp(*i, value) == false && comp(value, *i) == false
COMPLEXITYbinary_search performs at most log(last - first) + 2 comparisons.
EXAMPLE
//
// b_search.cpp
//
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
typedef vector<int>::iterator iterator;
int d1[10] = {0,1,2,2,3,4,2,2,6,7};
//
// Set up a vector
//
vector<int> v1(d1,d1 + 10);
//
// Try binary_search variants
//
sort(v1.begin(),v1.end());
bool b1 = binary_search(v1.begin(),v1.end(),3);
bool b2 =
binary_search(v1.begin(),v1.end(),11,less<int>());
//
// Output results
//
cout << "In the vector: ";
copy(v1.begin(),v1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << "The number 3 was "
<< (b1 ? "FOUND" : "NOT FOUND");
cout << endl << "The number 11 was "
<< (b2 ? "FOUND" : "NOT FOUND") << endl;
return 0;
}
Program OutputIn the vector: 0 1 2 2 2 2 3 4 6 7The number 3 was FOUNDThe number 11 was NOT FOUNDWARNINGS
If your compiler does not support default template parameters, then you
always need to supply the Allocator template argument. For instance,
you have to write:
vector<int,allocator<int> >
instead of:
vector<int>
If your compiler does not support namespaces, then you do not need the
using declaration for std.
SEE ALSO
equal_range, lower_bound, upper_bound
Rogue Wave Software 02 Apr 1998 binary_search(3C++)