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.
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
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.
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
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_searchdoes not give the position. Uselower_boundand compare, as init != 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 ofstd::setandstd::mapinstead on those. - Associative containers:
set::lower_bound,upper_boundandequal_rangehave the same meaning and are faster than the free functions on astd::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_rangereturns thelower_bound/upper_boundpair in one call. - Ranges:
std::ranges::binary_search,lower_bound,upper_bound(C++20) accept a projection.
Related
std::equal_range,std::find,std::sort,std::partition(partition_point),std::set- Lessons: Searching and sorting algorithms