std::lower_bound Recipes
`std::lower_bound` returns an iterator to the first element NOT less than a target in a sorted range, while `std::upper_bound` returns the first element strictly greater. This snippet shows how to use both for sorted-insertion, range-counting, and predicate-based binary search via the comparator overload. All run in O(log n) on random-access iterators.
493 views
14
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v = {1, 2, 4, 4, 4, 7, 9};
// lower_bound: first element NOT less than target. For 4: index 2.
auto lo = std::lower_bound(v.begin(), v.end(), 4);
// upper_bound: first element strictly greater than target. For 4: index 5.
auto hi = std::upper_bound(v.begin(), v.end(), 4);
std::cout << "lower idx=" << (lo - v.begin())
<< " upper idx=" << (hi - v.begin()) << "\n";
std::cout << "count of 4 = " << (hi - lo) << "\n";
// Containment test:
bool has5 = (std::lower_bound(v.begin(), v.end(), 5) != v.end()) &&
*std::lower_bound(v.begin(), v.end(), 5) == 5;
std::cout << "has 5? " << (has5 ? "yes" : "no") << "\n";
return 0;
}Both functions assume the input range is already sorted (or at least partitioned by the predicate); the result on an unsorted range is unspecified. The half-open interval [lower_bound, upper_bound) is exactly the run of elements equal to the target, so upper - lower gives the count of duplicates in O(log n). For a contains-check, compare *lower_bound with the target after verifying the iterator is not at end(). std::binary_search exists for this case but only returns a bool; lower_bound is more useful because you keep the iterator for further work.
#include <iostream>
#include <vector>
#include <algorithm>
void demoInsert() {
std::vector<int> v = {2, 5, 8};
int x = 6;
auto pos = std::lower_bound(v.begin(), v.end(), x);
v.insert(pos, x);
for (int n : v) std::cout << n << " ";
std::cout << "\n"; // 2 5 6 8
// Repeating: keeps the vector sorted as a maintained data structure.
for (int y : {3, 9, 1, 4}) {
v.insert(std::lower_bound(v.begin(), v.end(), y), y);
}
for (int n : v) std::cout << n << " ";
std::cout << "\n"; // 1 2 3 4 5 6 8 9
}
int main() {
demoInsert();
return 0;
}To insert into a sorted vector while keeping it sorted, find the insertion point with lower_bound then call insert. The lookup is O(log n) but the insert is O(n) because the tail must shift; the amortised cost is therefore not better than appending and re-sorting once, but it is great for small vectors that need to stay sorted at all times (active-task lists, displayed leaderboards). For frequent insertions and deletions in the middle, switch to std::set or std::multiset, which give O(log n) for everything but lose cache locality.
#include <iostream>
#include <vector>
#include <algorithm>
void demoPredicate() {
std::vector<int> v = {1, 3, 5, 7, 9, 11, 13};
// The 4th overload takes a comparator. Useful when you want to search
// not for equality but for a monotone predicate boundary.
// Find the first element >= 6 using a custom "less" comparator equivalent
// to the default (shown for illustration; the default form works here):
auto it = std::lower_bound(v.begin(), v.end(), 6,
[](int a, int b) { return a < b; });
std::cout << "first >= 6 is " << *it << "\n"; // 7
// The general technique: if you can write a monotone predicate `p(x)` that
// is false then becomes true once and stays true, std::partition_point
// finds the boundary in O(log n). Here: first element where x*x > 30.
auto cut = std::partition_point(v.begin(), v.end(),
[](int x) { return x * x <= 30; });
std::cout << "first whose square > 30 is " << *cut << "\n"; // 7 (7*7=49)
}
int main() {
demoPredicate();
return 0;
}The comparator overload of lower_bound lets you customise what 'less than' means, useful when searching by a key extracted from a struct (a.id < b.id). When your search criterion is a monotone predicate rather than an ordering on a key, reach for std::partition_point instead: it expects the range to be partitioned (predicate true for a prefix, false for the suffix, or vice versa) and returns the boundary in O(log n). Together these cover the full set of binary-search problems: ordered-key search, range-equal queries, and predicate boundaries. Always confirm the precondition (sorted or partitioned) before trusting the result.