binary_search


Category: algorithms	Component type: function

Prototype

Binary_search is an overloaded name; there are actually two binary_search functions.

template <class ForwardIterator
class LessThanComparable>
bool binary_search(ForwardIterator first
ForwardIterator last

                   const LessThanComparable& value);

template <class ForwardIterator
class T
class StrictWeakOrdering>
bool binary_search(ForwardIterator first
ForwardIterator last
const T& value

                   StrictWeakOrdering comp);

Description

Binary_search is a version of binary search: it attempts to find the element value in an ordered range [first last) It returns true if an element that is equivalent to [1] value is present in [first last) and false if no such element exists. [2] The first version of binary_search uses operator< for comparison and the second uses the function object comp.

Specifically the first version returns true if and only if there exists an iterator i in [first last) such that *i < value and value < *i are both false. The second version returns true if and only if there exists an iterator i in [first last) such that comp(*i value) and comp(value *i) are both false.

Definition

Defined in the standard header algorithm and in the nonstandard backward-compatibility header algo.h.

Requirements on types

For the first version:

ForwardIterator is a model of Forward Iterator.
LessThanComparable is a model of LessThan Comparable.
The ordering on objects of type LessThanComparable is a strict weak ordering as defined in the LessThan Comparable requirements.
ForwardIterator's value type is the same type as LessThanComparable.

For the second version:

ForwardIterator is a model of Forward Iterator.
StrictWeakOrdering is a model of Strict Weak Ordering.
ForwardIterator's value type is the same type as T.
ForwardIterator's value type is convertible to StrictWeakOrdering's argument type.

Preconditions

For the first version:

[first last) is a valid range.
[first last) is ordered in ascending order according to operator<. That is for every pair of iterators i and j in [first last) such that i precedes j *j < *i is false.

For the second version:

[first last) is a valid range.
[first last) is ordered in ascending order according to the function object comp. That is for every pair of iterators i and j in [first last) such that i precedes j comp(*j *i) is false.

Complexity

The number of comparisons is logarithmic: at most log(last - first) + 2. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise the number of steps is proportional to last - first. [3]

Example

int main()
{
  int A[] = { 1
2
3
3
3
5
8 };
  const int N = sizeof(A) / sizeof(int);

  for (int i = 1; i <= 10; ++i) {
    cout << "Searching for " << i << ": "
         << (binary_search(A
A + N
i) ? "present" : "not present") << endl;
  }
}

The output is:

Searching for 1: present
Searching for 2: present
Searching for 3: present
Searching for 4: not present
Searching for 5: present
Searching for 6: not present
Searching for 7: not present
Searching for 8: present
Searching for 9: not present
Searching for 10: not present

Notes

[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is there might be values x and y such that x < y x > y and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Finding value in the range [first last) then doesn't mean finding an element that is equal to value but rather one that is equivalent to value: one that is neither greater than nor less than value. If you're using a total ordering however (if you're using strcmp for example or if you're using ordinary arithmetic comparison on integers) then you can ignore this technical distinction: for a total ordering equality and equivalence are the same.

[2] Note that this is not necessarily the information you are interested in! Usually if you're testing whether an element is present in a range you'd like to know where it is (if it's present) or where it should be inserted (if it's not present). The functions lower_bound upper_bound and equal_range provide this information.

[3] This difference between Random Access Iterators and Forward Iterators is simply because advance is constant time for Random Access Iterators and linear time for Forward Iterators.