On a sorted C++ vector, how do std::binary_search, std::lower_bound, std::upper_bound and std::equal_range differ?
answer
- bool versus iterator
- first not-less, first greater
- a pair of both bounds
- same comparator as the sort
basics
~20 sstd::binary_search only answers whether a value is present. std::lower_bound returns the first position not less than the value, std::upper_bound the first position greater than it, and std::equal_range returns both, bracketing every equivalent element. All need data ordered by the same comparator.
solid answer
~40 sAll four do a logarithmic number of comparisons on a range that is **partitioned** by the search key, which a range sorted with the same comparator always is. `std::binary_search` returns a `bool` and nothing else, so you cannot get the position from it. `std::lower_bound(first, last, v)` returns the first iterator whose element is not less than `v`: the element itself if present, otherwise where `v` would be inserted. `std::upper_bound` returns the first element greater than `v`. `std::equal_range` returns the pair `{lower_bound, upper_bound}`, so `last - first` of that pair counts the matches. For a leaderboard sorted ascending, `scores.end() - upper_bound(..., s)` is the number of scores beating `s`. Searching with a different comparator than the one used to sort, or on unsorted data, breaks the precondition and the result is meaningless.
code
cpp · 22 lines#include <algorithm>
#include <iostream>
#include <vector>
int main() {
// scores sorted ascending
std::vector<int> scores{120, 300, 450, 450, 450, 610, 980};
bool has450 = std::binary_search(scores.begin(), scores.end(), 450);
auto lo = std::lower_bound(scores.begin(), scores.end(), 450); // first >= 450
auto hi = std::upper_bound(scores.begin(), scores.end(), 450); // first > 450
auto [first, last] = std::equal_range(scores.begin(), scores.end(), 450);
std::cout << std::boolalpha << has450 << '\n'
<< "lower_bound index " << (lo - scores.begin()) << '\n'
<< "upper_bound index " << (hi - scores.begin()) << '\n'
<< "count of 450: " << (last - first) << '\n'
<< "scores beating 450: " << (scores.end() - hi) << '\n';
auto ins = std::lower_bound(scores.begin(), scores.end(), 500);
std::cout << "500 would go at index " << (ins - scores.begin()) << '\n';
}go deeper
Recall that binary_search returns only a bool and that lower_bound returns an iterator to the first element not less than the value.
Explain lower versus upper bound, equal_range as the pair of both, and the precondition that the data is ordered by the same comparator.
Catch comparator argument-order bugs, mismatched sort and search comparators, and free lower_bound calls on node-based containers that turn logarithmic lookups linear.
Weigh a sorted vector with lower_bound against an ordered or hashed container for each lookup workload, based on how often it is updated versus queried.
## The precondition: partitioned by the key The binary search algorithms do not check that the range is sorted. The standard states a weaker precondition: the elements must be **partitioned** with respect to the comparison against the searched value - every element for which `comp(e, value)` is true comes before every element for which it is false. A range sorted with the same comparator satisfies this for every value. Two consequences: - **Same comparator.** A vector sorted descending with `std::greater<>{}` must be searched with `std::greater<>{}` too; searching it with the default `operator<` gives wrong positions. - **No checking.** Unsorted input does not throw or assert in a normal build; you just get an answer that means nothing. ## Four functions, four answers | Call | Returns | Meaning on ascending data | |---|---|---| | `std::binary_search(f, l, v)` | `bool` | is an element equivalent to `v` present? | | `std::lower_bound(f, l, v)` | iterator | first element **not less** than `v` (`>= v`) | | `std::upper_bound(f, l, v)` | iterator | first element **greater** than `v` (`> v`) | | `std::equal_range(f, l, v)` | `pair` of iterators | `{lower_bound, upper_bound}` | Every one of them may return `last`. `lower_bound` returns `last` when all elements are less than `v`; dereferencing that is undefined behaviour, so check first. ## Using them on a leaderboard Keep scores in a `std::vector<int>` sorted ascending. Then: 1. **Membership:** `std::binary_search(s.begin(), s.end(), 450)`. Fine for yes or no, useless if you need the element afterwards. 2. **Find the element:** `auto it = std::lower_bound(s.begin(), s.end(), 450); if (it != s.end() && *it == 450) ...`. Both checks are needed: `lower_bound` returns the insertion point when the value is absent. 3. **Count ties:** `auto [lo, hi] = std::equal_range(s.begin(), s.end(), 450); hi - lo;`. 4. **Rank query:** the number of strictly higher scores is `s.end() - std::upper_bound(s.begin(), s.end(), 450)`, so the rank is that plus one. 5. **Sorted insert:** `s.insert(std::upper_bound(s.begin(), s.end(), v), v);` keeps the vector sorted, placing `v` after existing equal values. ## Searching by a member For a vector of structs sorted by `score`, the comparator can take mixed argument types, because `lower_bound` calls `comp(element, value)` and `upper_bound` calls `comp(value, element)`: ```cpp auto it = std::lower_bound(board.begin(), board.end(), 450, [](const Entry& e, int s) { return e.score < s; }); ``` The argument order is the classic trap: a lambda written `(int, const Entry&)` compiles for `upper_bound` but not for `lower_bound`. `std::equal_range` calls both forms, so it needs a comparator that accepts both orders, such as a function object with two `operator()` overloads. ## Complexity and iterator category - `lower_bound`, `upper_bound` and `binary_search` make at most `log2(N) + O(1)` comparisons; `equal_range` at most `2 * log2(N) + O(1)`. - They accept **forward iterators**. On a `std::list` the comparisons stay logarithmic, but advancing the iterator to the middle is linear, so the total work is linear. - On a `std::set` or `std::map`, call the member `lower_bound` instead: the free function cannot use the tree structure and walks the iterators. ## The general form: std::partition_point All four functions are special cases of one idea: find the boundary in a range where a predicate flips from true to false. `std::partition_point(first, last, pred)` (C++11) exposes that idea directly and takes a **unary** predicate, which removes the argument-order trap: ```cpp auto firstAbove = std::partition_point(s.begin(), s.end(), [](int x) { return x <= 450; }); // same as upper_bound(450) ``` It is handy when the condition is not a comparison against a single value - the first record whose timestamp falls after a cutoff, the first bucket whose cumulative size exceeds a budget. The precondition is the same: the range must be partitioned by `pred`, every true before every false. ## Picking one Use `binary_search` only for a pure membership test. Use `lower_bound` when you need the position of a value or its insertion point, `upper_bound` for "strictly after", and `equal_range` when you need the whole run of equivalent elements.
- Why does std::lower_bound with a lambda taking (int, const Entry&) fail to compile?`std::lower_bound` evaluates `comp(element, value)`, so the comparator's first parameter must accept the element type and the second the searched value: `(const Entry&, int)`. `std::upper_bound` calls `comp(value, element)`, the opposite order. A function object with both `operator()` overloads serves `equal_range`, which calls both forms.
- Your vector is sorted descending with std::greater<>. How do you find the first score not greater than 450?Pass the same comparator to the search: `std::lower_bound(v.begin(), v.end(), 450, std::greater<>{})`. Under `greater`, "not less" means "not greater", so it returns the first element `<= 450`. Searching the descending vector with the default `operator<` violates the partition precondition and returns a meaningless position.
- Using std::binary_search and expecting an iterator to the match
- Dereferencing lower_bound's result without checking for end()
- Assuming lower_bound returns end() when the value is absent
- Searching a descending vector with the default operator<
- Believing the algorithms verify that the range is sorted
- Calling free std::lower_bound on a std::set instead of the member