Home / C++ / Binary search and STL search algorithms

C++ PROGRAMMING · 13 MIN STUDY

Binary search and STL search algorithms

Use lower_bound, upper_bound, equal_range, and binary_search on correctly ordered ranges.

Learning objectives

  • Explain why binary search requires a range partitioned by the searched value.
  • Use binary_search, lower_bound, upper_bound, and equal_range.
  • Interpret returned iterators safely.
  • Understand logarithmic comparisons and iterator movement costs.

Prerequisites: understand std::vector, iterators, sorting, and comparator basics. Review Vectors, Iterator categories, and STL algorithms first.

Binary search prerequisite

Binary search repeatedly eliminates half of the remaining search space. The range must already be sorted using the same ordering rule, or at least partitioned appropriately for the searched value. Applying it to unsorted data produces unreliable results.

#include <algorithm>
#include <vector>
std::vector<int> values{1, 3, 3, 3, 7, 9};
bool exists = std::binary_search(values.begin(), values.end(), 3);
auto first = std::lower_bound(values.begin(), values.end(), 3);
auto after = std::upper_bound(values.begin(), values.end(), 3);

What each algorithm returns

  • binary_search returns a Boolean: whether an equivalent value exists.
  • lower_bound returns the first position whose value is not less than the target.
  • upper_bound returns the first position whose value is greater than the target.
  • equal_range returns both boundaries as a pair of iterators.

Count duplicates

auto range = std::equal_range(values.begin(), values.end(), 3);
auto count = range.second - range.first; // valid for vector iterators
// count is 3

For random-access iterators, subtracting the iterators gives the number of matching elements. For a generic iterator category, use std::distance(range.first, range.second); on non-random-access iterators, distance takes linear time.

Insert while preserving order

auto position = std::lower_bound(values.begin(), values.end(), 5);
values.insert(position, 5);

Finding the position takes logarithmic comparisons, but inserting into the middle of a vector still shifts elements and is O(n). Do not confuse search complexity with the total cost of the operation.

Custom ordering

When using a custom comparator, the range must be ordered consistently with that comparator, and the same comparator must be passed to the search algorithm.

#include <functional>
std::vector<int> descending{9, 7, 5, 3, 1};
auto it = std::lower_bound(descending.begin(), descending.end(), 5,
                           std::greater<int>{});

Complexity

These algorithms make O(log n) comparisons. With random-access iterators, they also require O(log n) iterator movement. With forward or bidirectional iterators, the number of comparisons is logarithmic but total iterator increments can be linear.

Common mistakes

  • Searching an unsorted range.
  • Sorting ascending but searching with a descending comparator.
  • Dereferencing a returned iterator without checking it against end.
  • Assuming a vector insertion after lower_bound is logarithmic overall.

Practice

  1. Find the first occurrence of 12 in a sorted vector.
  2. Count how many times 7 appears using equal_range.
  3. What does lower_bound return if every element is smaller than the target?
  4. Why is vector insertion still O(n) after binary search?
Show solutions
  1. Use lower_bound; check the iterator is not end and that *it == 12.
  2. Subtract the two returned iterators for vector, or use distance generically.
  3. The end iterator.
  4. Elements after the insertion point must be shifted.

Summary

Binary-search algorithms need an ordered or partitioned range. lower_bound and upper_bound define boundaries; equal_range returns both. Search comparisons can be logarithmic even when the surrounding container operation is not.

References