C++ / ITERATORS, ALGORITHMS, AND RANGES
Sorting, searching, and binary search helpers
Sort ranges with a strict comparator and use lower_bound, upper_bound, and equal_range to get positions, counts, and insertion points in log time.
What you will learn
- std::sort is unstable and needs a strict comparator; stable_sort preserves ties
- Get positions and counts from lower_bound, upper_bound, and equal_range
- Search with the same comparator used to sort, or answers are silently wrong
- Use nth_element or partial_sort for a median or top-k instead of a full sort
Understanding Sorting, searching, and binary search helpers
std::sort needs random-access iterators because it keeps picking a pivot and jumping to the middle of the range, which is why std::list carries its own member sort instead. The comparator you hand it must be a strict weak ordering: comp(a, a) has to be false, and comp(a, b) and comp(b, a) must never both be true. Implementations lean on that promise to drop bounds checks inside the partition loop, so a <= comparator does not merely mis-order elements, it can let the loop walk off the end of the array. std::sort also makes no promise about the relative order of elements that compare equal; std::stable_sort does, paying for it with a temporary buffer and an extra log factor if that buffer cannot be allocated.
The binary search family, lower_bound, upper_bound, equal_range, and binary_search, does not strictly require a sorted range. Each asks one yes/no question of every element it visits and only requires that the answer flip once across the range; sorting by the same comparator is simply the easiest way to arrange that. lower_bound evaluates comp(element, value) and returns the first position where it is false, while upper_bound evaluates comp(value, element) and returns the first position where it is true. Because each one always compares in a fixed direction, you can search a container of structs with a bare key by writing a comparator that takes the element on one side and the key on the other.
Prefer the bound functions over binary_search: binary_search discards the position it located and hands back a bool, whereas lower_bound gives you the iterator, hi - lo gives the number of equal elements, and that same iterator is the correct insertion point when the value is absent. That is why "is it there?" and "where would it go?" are one call, not two. The halving counts comparisons, not iterator steps, so std::lower_bound on a std::set or std::list still does O(n) pointer chasing; use the container's member lower_bound there. When you need less than a full ordering, std::nth_element places one element correctly and merely partitions around it in linear time on average, and std::partial_sort orders only a prefix.
<algorithm>
<iostream>
<vector>
int main() {
std::vector<int> v{5, 3, 9, 1, 3, 7, 3};
std::sort(v.begin(), v.end()); // O(n log n), ties in any order
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
auto lo = std::lower_bound(v.begin(), v.end(), 3); // first element not < 3
auto hi = std::upper_bound(v.begin(), v.end(), 3); // first element > 3
std::cout << "first 3 at index " << lo - v.begin() << '\n';
std::cout << "end of the 3s at index " << hi - v.begin() << '\n';
std::cout << "how many 3s: " << hi - lo << '\n';
std::cout << std::boolalpha
<< "contains 4? " << std::binary_search(v.begin(), v.end(), 4) << '\n';
// the iterator that answers "where is it?" also answers "where would it go?"
v.insert(std::lower_bound(v.begin(), v.end(), 4), 4);
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}Binary search needs a range partitioned by the exact comparison you search with, and the bound functions return positions rather than a bare yes or no.
Worked examples
Stable sort plus a heterogeneous search key
Sorts records by score descending, keeps tied records in input order, then searches that descending range with a plain int.
<algorithm>
<iostream>
<string>
<vector>
struct Player { std::string name; int score; };
int main() {
std::vector<Player> ps{{"ana", 7}, {"bo", 9}, {"cy", 7}, {"di", 9}};
auto by_score_desc = [](const Player& a, const Player& b) {
return a.score > b.score;
};
std::stable_sort(ps.begin(), ps.end(), by_score_desc);
for (const Player& p : ps) std::cout << p.name << ':' << p.score << ' ';
std::cout << '\n';
auto it = std::lower_bound(ps.begin(), ps.end(), 8,
[](const Player& p, int s) { return p.score > s; });
std::cout << "first score below 8: " << it->name << '\n';
}Example explained
Line 1return a.score > b.score is strict: two 9s compare false both ways, so they count as ties.
Line 2stable_sort keeps bo ahead of di because that was their input order; plain std::sort may emit either.
Line 3lower_bound's comparator receives the element first and the key second, so a bare int can be compared against a Player.
Line 4The call returns the first position where the descending run stops being above 8, which is ana, after about two comparisons.
Top-k and median without sorting everything
Shows what partial_sort and nth_element actually guarantee about the elements they do not fully order.
<algorithm>
<iostream>
<vector>
int main() {
std::vector<int> v{42, 7, 19, 3, 88, 25, 11, 60};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
std::cout << "3 smallest: " << v[0] << ' ' << v[1] << ' ' << v[2] << '\n';
std::vector<int> w{42, 7, 19, 3, 88, 25, 11, 60};
std::nth_element(w.begin(), w.begin() + 4, w.end());
std::cout << "5th smallest: " << w[4] << '\n';
std::cout << std::boolalpha << "split around it holds: "
<< std::is_partitioned(w.begin(), w.end(),
[pivot = w[4]](int x) { return x < pivot; })
<< '\n';
}Example explained
Line 1partial_sort orders only the first three positions and leaves the remaining five in an unspecified order, costing O(n log k).
Line 2nth_element guarantees just one thing: w[4] holds the value a full sort would put at index 4, found in linear time on average.
Line 3is_partitioned verifies the usable side effect: nothing before index 4 is larger than w[4], and nothing after it is smaller.
Line 4Printing w[0] after nth_element would be a bug, since the order inside each half is not specified.
Important notes
std::binary_search on a std::set or std::map compiles but ignores the tree structure, doing O(n) iterator steps; the member find and lower_bound are the O(log n) versions.
Sorting a vector<double> that contains NaN breaks the ordering contract, because NaN < x and x < NaN are both false, making NaN compare equivalent to everything; the result is a scrambled range, not just a NaN in an odd place.
Common mistakes
Writing the comparator as return a.score <= b.score to "include equal elements": that violates the strict ordering requirement and lets std::sort read past the end of the range, often crashing only once the input is large enough to leave the small-range insertion sort path.
Sorting with a custom comparator and then calling lower_bound or binary_search without it: the default < disagrees with the order actually in the range, so the search returns a wrong position with no error or warning.
Dereferencing lower_bound's result without checking it: on a miss it points at the next larger element, and when the key exceeds every element it equals end(), so *it is undefined behaviour.
Try it yourself
Change, predict, then run
Given std::vector<int> v{4, 8, 15, 16, 23, 42}, write insert_sorted(std::vector<int>&, int) that uses std::lower_bound to insert while keeping the vector sorted, then call it with 15 and 50 and print the vector to confirm the duplicate 15 lands next to the existing one.
Open the C++ workspaceCheck your understanding
A vector is sorted in descending order and you call std::lower_bound(v.begin(), v.end(), 5) with no comparator. What happens?
- It compiles and runs, but the returned iterator is meaningless because the range is not partitioned by element < 5
- It returns the first element less than or equal to 5, since lower_bound compares in both directions
- It fails to compile, because lower_bound requires an explicit comparator for a descending range
- It always returns v.end(), since no element satisfies the ascending precondition
Show answer
lower_bound is specified as the first position where element < value is false, and it can only find that position by halving if the answer flips exactly once from true to false. A descending range flips it the other way, so the halving takes the wrong branch and the result is arbitrary. Option 2 is tempting but wrong: lower_bound only ever evaluates comp(element, value), never the reverse, so it cannot detect the direction. Nothing fails to compile either, since int < int is perfectly valid; the partition requirement is a runtime contract the type system does not check.