# Binary search algorithms

## Detailed Description

These algorithms are variations of a classic binary search. They all assume that the sequence being searched is already sorted.

The number of comparisons will be logarithmic (and as few as possible). The number of steps through the sequence will be logarithmic for random-access iterators (e.g., pointers), and linear otherwise.

The LWG has passed Defect Report 270, which notes: The proposed resolution reinterprets binary search. Instead of thinking about searching for a value in a sorted range, we view that as an important special case of a more general algorithm: searching for the partition point in a partitioned range. We also add a guarantee that the old wording did not: we ensure that the upper bound is no earlier than the lower bound, that the pair returned by equal_range is a valid range, and that the first part of that pair is the lower bound.

The actual effect of the first sentence is that a comparison functor passed by the user doesn't necessarily need to induce a strict weak ordering relation. Rather, it partitions the range.

## Functions

- template<typename _ForwardIterator, typename _Tp, typename _Compare> bool std::binary_search (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
- template<typename _ForwardIterator, typename _Tp> bool std::binary_search (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val)
- template<typename _ForwardIterator, typename _Tp, typename _Compare> pair< _ForwardIterator, _ForwardIterator > std::equal_range (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
- template<typename _ForwardIterator, typename _Tp> pair< _ForwardIterator, _ForwardIterator > std::equal_range (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val)
- template<typename _ForwardIterator, typename _Tp, typename _Compare> _ForwardIterator std::lower_bound (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
- template<typename _ForwardIterator, typename _Tp> _ForwardIterator std::lower_bound (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val)
- template<typename _ForwardIterator, typename _Tp, typename _Compare> _ForwardIterator std::upper_bound (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
- template<typename _ForwardIterator, typename _Tp> _ForwardIterator std::upper_bound (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val)

## Function Documentation

template<typename _ForwardIterator, typename _Tp, typename _Compare>

bool std::binary_search | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | const _Tp & | __val,
|  | _Compare | __comp |
| ) |  |  |

Determines whether an element exists in a range.

Parameters:

  | first | An iterator.
  | last | Another iterator.
  | val | The search term.
  | comp | A functor to use for comparisons.

Returns:
  True if val (or its equivelent) is in [first,last ].

Note that this does not actually return an iterator to val. For that, use std::find or a container's specialized find member functions.

The comparison function should have the same effects on ordering as the function used for the initial sort.

Definition at line 4260 of file stl_algo.h.

References __glibcxx_function_requires, __glibcxx_requires_partitioned_pred, and std::lower_bound().

template<typename _ForwardIterator, typename _Tp>

bool std::binary_search | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | const _Tp & | __val |
| ) |  |  |

Determines whether an element exists in a range.

Parameters:

  | first | An iterator.
  | last | Another iterator.
  | val | The search term.

Returns:
  True if val (or its equivelent) is in [first,last ].

Note that this does not actually return an iterator to val. For that, use std::find or a container's specialized find member functions.

Definition at line 4228 of file stl_algo.h.

References __glibcxx_function_requires, __glibcxx_requires_partitioned, and std::lower_bound().

template<typename _ForwardIterator, typename _Tp, typename _Compare>

pair<_ForwardIterator, _ForwardIterator> std::equal_range | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | const _Tp & | __val,
|  | _Compare | __comp |
| ) |  |  |

Finds the largest subrange in which val could be inserted at any place in it without changing the ordering.

Parameters:

  | first | An iterator.
  | last | Another iterator.
  | val | The search term.
  | comp | A functor to use for comparisons.

Returns:
  An pair of iterators defining the subrange.

This is equivalent to

        std::make_pair(lower_bound(first, last, val, comp),
                       upper_bound(first, last, val, comp))

but does not actually call those functions.

Definition at line 4170 of file stl_algo.h.

References __glibcxx_function_requires, __glibcxx_requires_partitioned_pred, std::advance(), std::distance(), std::lower_bound(), and std::upper_bound().

Referenced by std::__debug::set< _Key, _Compare, _Allocator >::equal_range(), std::__debug::multiset< _Key, _Compare, _Allocator >::equal_range(), std::__debug::multimap< _Key, _Tp, _Compare, _Allocator >::equal_range(), std::__debug::map< _Key, _Tp, _Compare, _Allocator >::equal_range(), __gnu_cxx::__debug::hash_set< _Value, _HashFcn, _EqualKey, _Alloc >::equal_range(), __gnu_cxx::__debug::hash_multiset< _Value, _HashFcn, _EqualKey, _Alloc >::equal_range(), __gnu_cxx::__debug::hash_multimap< _Value, _Tp, _HashFcn, _EqualKey, _Alloc >::equal_range(), and __gnu_cxx::__debug::hash_map< _Value, _Tp, _HashFcn, _EqualKey, _Alloc >::equal_range().

template<typename _ForwardIterator, typename _Tp>

pair<_ForwardIterator, _ForwardIterator> std::equal_range | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | const _Tp & | __val |
| ) |  |  |

Finds the largest subrange in which val could be inserted at any place in it without changing the ordering.

Parameters:

  | first | An iterator.
  | last | Another iterator.
  | val | The search term.

Returns:
  An pair of iterators defining the subrange.

This is equivalent to

        std::make_pair(lower_bound(first, last, val),
                       upper_bound(first, last, val))

but does not actually call those functions.

Definition at line 4109 of file stl_algo.h.

References __glibcxx_function_requires, __glibcxx_requires_partitioned, std::advance(), std::distance(), std::lower_bound(), and std::upper_bound().

template<typename _ForwardIterator, typename _Tp, typename _Compare>

_ForwardIterator std::lower_bound | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | const _Tp & | __val,
|  | _Compare | __comp |
| ) |  |  |

Finds the first position in which val could be inserted without changing the ordering.

Parameters:

  | first | An iterator.
  | last | Another iterator.
  | val | The search term.
  | comp | A functor to use for comparisons.

Returns:
  An iterator pointing to the first element "not less than" val, or end() if every element is less than val.

The comparison function should have the same effects on ordering as the function used for the initial sort.

Definition at line 2934 of file stl_algo.h.

References __glibcxx_function_requires, __glibcxx_requires_partitioned_pred, std::advance(), and std::distance().

Referenced by std::map< _Key, _Tp, _Compare, _Allocator >::at(), and std::map< _Key, _Tp, _Compare, _Allocator >::operator[]().

template<typename _ForwardIterator, typename _Tp>

_ForwardIterator std::lower_bound | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | const _Tp & | __val |
| ) |  |  |

Finds the first position in which val could be inserted without changing the ordering.

Parameters:

  | first | An iterator.
  | last | Another iterator.
  | val | The search term.

Returns:
  An iterator pointing to the first element "not less than" val, or end() if every element is less than val.

Definition at line 2884 of file stl_algo.h.

References __glibcxx_function_requires, __glibcxx_requires_partitioned, std::advance(), and std::distance().

Referenced by std::__merge_adaptive(), std::__merge_without_buffer(), __gnu_cxx::__stl_next_prime(), std::tr1::__detail::_Prime_rehash_policy::_M_bkt_for_elements(), std::tr1::__detail::_Prime_rehash_policy::_M_need_rehash(), std::tr1::__detail::_Prime_rehash_policy::_M_next_bkt(), std::binary_search(), and std::equal_range().

template<typename _ForwardIterator, typename _Tp, typename _Compare>

_ForwardIterator std::upper_bound | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | const _Tp & | __val,
|  | _Compare | __comp |
| ) |  |  |

Finds the last position in which val could be inserted without changing the ordering.

Parameters:

  | first | An iterator.
  | last | Another iterator.
  | val | The search term.
  | comp | A functor to use for comparisons.

Returns:
  An iterator pointing to the first element greater than val, or end() if no elements are greater than val.

The comparison function should have the same effects on ordering as the function used for the initial sort.

Definition at line 3031 of file stl_algo.h.

References __glibcxx_function_requires, __glibcxx_requires_partitioned_pred, std::advance(), and std::distance().

template<typename _ForwardIterator, typename _Tp>

_ForwardIterator std::upper_bound | ( | _ForwardIterator | __first,
|  | _ForwardIterator | __last,
|  | const _Tp & | __val |
| ) |  |  |

Finds the last position in which val could be inserted without changing the ordering.

Parameters:

  | first | An iterator.
  | last | Another iterator.
  | val | The search term.

Returns:
  An iterator pointing to the first element greater than val, or end() if no elements are greater than val.

Definition at line 2981 of file stl_algo.h.

References __glibcxx_function_requires, __glibcxx_requires_partitioned, std::advance(), and std::distance().

Referenced by std::__merge_adaptive(), std::__merge_without_buffer(), and std::equal_range().