[equal.range]

# 26 Algorithms library [[algorithms]](./#algorithms)

## 26.8 Sorting and related operations [[alg.sorting]](alg.sorting#equal.range)

### 26.8.4 Binary search [[alg.binary.search]](alg.binary.search#equal.range)

#### 26.8.4.4 equal_range [equal.range]

[🔗](#lib:equal_range)

`template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
  constexpr pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first,
                ForwardIterator last, const T& value);

template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type,
         class Compare>
  constexpr pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first,
                ForwardIterator last, const T& value,
                Compare comp);

template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S, class Proj = identity,
         class T = projected_value_t<I, Proj>,
         [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<const T*, projected<I, Proj>> Comp = ranges::less>
  constexpr subrange<I>
    ranges::equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity,
         class T = projected_value_t<iterator_t<R>, Proj>,
         [indirect_strict_weak_order](indirectcallable.indirectinvocable#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<const T*, projected<iterator_t<R>, Proj>> Comp =
           ranges::less>
  constexpr borrowed_subrange_t<R>
    ranges::equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});
`

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9538)

Let comp be less{} andproj be identity{} for overloads with no parameters by those names[.](#1.sentence-1)

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9543)

*Preconditions*: The elements e of [first, last)
are partitioned with respect to the expressionsbool(invoke(comp, invoke(proj, e), value)) and!bool(invoke(comp, value, invoke(proj, e)))[.](#2.sentence-1)

Also, for all elements e of [first, last),bool(comp(e, value)) implies !bool(comp(​value, e)) for the overloads in namespace std[.](#2.sentence-2)

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9553)

*Returns*: 

- [(3.1)](#3.1)

For the overloads in namespace std:{lower_bound(first, last, value, comp),
 upper_bound(first, last, value, comp)}

- [(3.2)](#3.2)

For the overloads in namespace ranges:{ranges::lower_bound(first, last, value, comp, proj),
 ranges::upper_bound(first, last, value, comp, proj)}

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L9570)

*Complexity*: At most2∗log2(last - first)+O(1) comparisons and projections[.](#4.sentence-1)