# 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.

### See also

`lower_bound`, `upper_bound`, `equal_range`

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation