Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Algorithms

The std::binary_search, lower_bound and upper_bound algorithms

Reference for C++ binary_search, lower_bound and upper_bound: O(log n) search in sorted ranges, the returned iterators, custom comparators and pitfalls.

Three algorithms in <algorithm> do binary search on a sorted range. std::binary_search answers a yes/no question: is the value in the range? std::lower_bound returns an iterator to the first element that is not less than the value, and std::upper_bound returns an iterator to the first element that is greater than the value.

Together, lower_bound and upper_bound bracket all elements equal to a value, and they tell you where a new value must be inserted to keep the range sorted. On random-access ranges they take O(log n) comparisons. The input must be sorted by the same ordering you search with; otherwise the result is meaningless.

C++
auto it = std::lower_bound(v.begin(), v.end(), 42);   // first element >= 42
bool has = std::binary_search(v.begin(), v.end(), 42);

Try it

C++ Finding positions in a sorted vector

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ Custom comparator and searching by a key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

C++
template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value);

template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);

template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);

// each also exists with a trailing Compare comp argument
Name Description
first, last The half-open sorted range [first, last).
value The value to look for. It may have a different type from the elements if the comparator supports the mix.
comp Strict weak ordering. For lower_bound: comp(element, value). For upper_bound: comp(value, element).

Returns: binary_search returns a bool. lower_bound returns the first position where !(element < value); upper_bound the first where value < element. Both return last if there is no such element.

Errors / undefined behavior: if the range is not partitioned with respect to the comparison (in practice: not sorted by the same ordering), the behavior is undefined for the purposes of the guarantee, and the result is wrong.

Usage notes

  • Sorted input is a precondition. Binary search on unsorted data does not fail loudly; it returns garbage. Sort first, or use std::find.
  • binary_search does not give the position. Use lower_bound and compare, as in it != end && !(value < *it), when you need the element.
  • Complexity: O(log n) comparisons. The number of iterator steps is O(log n) for random-access iterators but O(n) for forward iterators such as std::list, so use the member functions of std::set and std::map instead on those.
  • Associative containers: set::lower_bound, upper_bound and equal_range have the same meaning and are faster than the free functions on a std::set.
  • Same ordering everywhere: the comparator must be the one used to sort the range. Searching a descending range needs std::greater.
  • Inserting in order: v.insert(std::lower_bound(...), x) keeps a vector sorted, at O(n) per insertion because of shifting.
  • Both ends at once: std::equal_range returns the lower_bound/upper_bound pair in one call.
  • Ranges: std::ranges::binary_search, lower_bound, upper_bound (C++20) accept a projection.