C++ Search Algorithms: find, binary_search, lower_bound, and upper_bound

By 0xmote · May 27, 2026 · 27 min read · Updated Sep 24, 2026 Intermediate tutorial

Key takeaways

Choose between linear find and binary search on sorted ranges; use lower_bound, upper_bound, and equal_range for positions and equal-key runs in C++.

What are search algorithms?

The C++ standard library splits searching into two families instead of giving you one general-purpose “search” function, and the split is not cosmetic — it reflects a trade-off you have to make consciously every time you look something up in a range. The linear family (std::find, std::find_if, std::find_if_not) makes no assumption about the data: it walks the range in order and stops at the first match, so it is correct on any range, sorted or not. The binary search family (std::binary_search, std::lower_bound, std::upper_bound, std::equal_range) is much faster — O(log n) instead of O(n) — but it buys that speed by assuming the range is already sorted according to the exact ordering you pass in (or operator< if you don’t pass one). That assumption is a precondition, not something the algorithm verifies at runtime. If it’s false, you don’t get an exception or an assertion failure — you get answers that are wrong in ways that can look almost correct, which is exactly why this family deserves careful understanding rather than a quick copy-paste.

Search family overview

Algorithm	Time	Sorted?	Role
`find`	O(n)	No	First equal value
`find_if`	O(n)	No	First pred true
`binary_search`	O(log n)	Yes	Existence
`lower_bound`	O(log n)	Yes	First not-before value
`upper_bound`	O(log n)	Yes	First after value
`equal_range`	O(log n)	Yes	Subrange of equal keys

Notice that only find and find_if return something you can use directly as a “did I find it” check via comparison to end(). binary_search collapses everything down to a bool, which is convenient when you only care about existence but throws away the position — and in practice you almost always want the position too, whether to read the matching element, insert next to it, or erase it. That’s why lower_bound and upper_bound exist, and why real code reaches for them far more often than for binary_search itself.

std::find and std::find_if

Basic find

#include <algorithm>
#include <vector>
#include <iostream>
std::vector<int> numbers = {1, 3, 5, 7, 9, 11};
// Find specific value
auto it = std::find(numbers.begin(), numbers.end(), 7);
if (it != numbers.end()) {
    std::cout << "Found: " << *it << " at index " 
              << std::distance(numbers.begin(), it) << "\n";
} else {
    std::cout << "Not found\n";
}

find_if with predicate

#include <algorithm>
#include <vector>
std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
// Find first even number
auto it = std::find_if(numbers.begin(), numbers.end(),
                       [](int x) { return x % 2 == 0; });
if (it != numbers.end()) {
    std::cout << "First even: " << *it << "\n";  // 2
}

find_if_not

// Find first NOT matching predicate
auto it = std::find_if_not(numbers.begin(), numbers.end(),
                           [](int x) { return x < 5; });
// Finds first element >= 5

find_if_not is easy to overlook, but it removes a common source of double-negative predicates. Writing find_if(..., [](int x){ return !(x < 5); }) works, but negating the condition inside the lambda instead of using the dedicated algorithm makes the intent harder to read, and it’s one more place a typo can flip the logic. None of these three linear algorithms know or care whether the range is sorted — that’s their whole appeal. If your data is small (a rough rule of thumb is a few dozen elements, though the honest answer is “measure it”), changes shape too often to justify keeping it sorted, or is genuinely unsorted and only needs a single lookup, find/find_if isn’t a lesser tool you settle for — it’s the correct one. The mistake I see more often than “using find on sorted data” is the opposite: reaching for binary_search on a range that gets rebuilt every loop iteration, where the cost of keeping it sorted dwarfs anything saved on the search itself.

Binary search algorithms

Critical: Range must be sorted first — and “sorted” means something more specific than it might seem, as the comparator section further down explains.

std::binary_search

Returns bool indicating existence:

#include <algorithm>
#include <vector>
std::vector<int> sorted = {1, 3, 5, 7, 9, 11, 13};
bool found = std::binary_search(sorted.begin(), sorted.end(), 7);
// true
bool notFound = std::binary_search(sorted.begin(), sorted.end(), 6);
// false

binary_search answers exactly one question — “is this value in here?” — and nothing else. It doesn’t tell you where the value is; there’s no overload that hands back an iterator, and internally it’s essentially lower_bound plus one extra comparison, after which the iterator is thrown away and only a bool survives. That’s fine when existence really is all you need (a set-membership check, a validation gate), but the moment you also need the index, need to insert next to the match, or need to check for duplicates, calling binary_search first and then a second search to recover the position is wasted work. Reach for lower_bound directly instead — it gives you the boolean for free (it != end() && *it == value) and the position in the same call.

std::lower_bound

Finds first position where element could be inserted maintaining order:

std::vector<int> sorted = {1, 3, 5, 5, 5, 7, 9};
auto it = std::lower_bound(sorted.begin(), sorted.end(), 5);
// Points to first 5
std::cout << "Index: " << std::distance(sorted.begin(), it) << "\n";  // 2
std::cout << "Value: " << *it << "\n";  // 5
// For value not present
auto it2 = std::lower_bound(sorted.begin(), sorted.end(), 6);
// Points to 7 (first element >= 6)

The name “lower_bound” is a little misleading if you expect it to mean “the largest value less than or equal to x.” In position terms it actually means the opposite: it’s the first place you could insert value without violating the ordering, i.e. the first element that is not less than value. When there are duplicates, that lands you on the first of the run — which is exactly why sorted.insert(lower_bound(...), value) in the third real-world example below always inserts before any existing equal elements rather than after them, a detail that matters if you rely on insertion order to break ties among equal keys (stable priority among same-priority tasks, for example).

std::upper_bound

Finds first position strictly greater than value:

std::vector<int> sorted = {1, 3, 5, 5, 5, 7, 9};
auto it = std::upper_bound(sorted.begin(), sorted.end(), 5);
// Points to 7 (first element > 5)
std::cout << "Index: " << std::distance(sorted.begin(), it) << "\n";  // 5
std::cout << "Value: " << *it << "\n";  // 7

upper_bound is lower_bound’s mirror image: it gives the first position strictly after every element equal to value, so [lower_bound(v), upper_bound(v)) is always the contiguous run of elements equal to v — possibly empty if v isn’t present, in which case both calls land on the same iterator. Getting lower_bound and upper_bound backwards is an easy mistake to make because the code still compiles and still “works” for the common case of no duplicates; it only surfaces once the data actually has repeated keys, which is exactly the kind of thing that slips past a quick manual test and only shows up later as a subtly wrong result in production (see “Mistake 3” below for a concrete case).

std::equal_range

Returns pair of iterators [lower_bound, upper_bound):

std::vector<int> sorted = {1, 3, 5, 5, 5, 7, 9};
auto [first, last] = std::equal_range(sorted.begin(), sorted.end(), 5);
std::cout << "Count of 5: " << std::distance(first, last) << "\n";  // 3
// Print all occurrences
for (auto it = first; it != last; ++it) {
    std::cout << *it << " ";
}
// Output: 5 5 5

equal_range is a convenience, not a different algorithm — most standard library implementations compute it by finding lower_bound first, then running a second binary search restricted to the remainder of the range to find upper_bound, so the whole operation stays O(log n) rather than doubling into two independent full-range searches. It’s most useful when you actually plan to iterate every element with a matching key, because it saves you from calling lower_bound and upper_bound separately and mismatching the boundary logic (see the --last correction needed in “Finding first/last occurrence” further down, which equal_range sidesteps entirely).

Real-world examples

User search by ID

#include <algorithm>
#include <vector>
#include <string>
struct User {
    int id;
    std::string name;
    
    bool operator<(const User& other) const {
        return id < other.id;
    }
};
std::vector<User> users = {
    {1, "Alice"},
    {3, "Bob"},
    {5, "Charlie"},
    {7, "David"}
};
// Must be sorted by id
std::sort(users.begin(), users.end());
// Binary search by id
User target{5, ""};
auto it = std::lower_bound(users.begin(), users.end(), target);
if (it != users.end() && it->id == 5) {
    std::cout << "Found: " << it->name << "\n";  // Charlie
}

Two things about this example are worth calling out because they’re the kind of detail that’s obvious once you’ve been bitten by it and invisible until then. First, target only sets id; name is left as an empty string. That’s fine here because operator< only compares id, so the search never touches name — but it means target isn’t a “real” User, just a probe value shaped enough to satisfy the comparator. If operator< ever grows a tiebreaker (sort by id, then by name) without updating every probe object built this way, the search silently starts comparing against whatever default value happens to be sitting in that second field. Second, lower_bound doesn’t guarantee a match — it guarantees the insertion point. The it->id == 5 check afterward is not defensive boilerplate you can skip; without it, an id that doesn’t exist gives you an iterator to the next-higher id (or end()), and dereferencing it unconditionally reads someone else’s user.

Range query

#include <algorithm>
#include <vector>
std::vector<int> timestamps = {100, 150, 200, 250, 300, 350, 400};
// Find all events between 180 and 320
auto start = std::lower_bound(timestamps.begin(), timestamps.end(), 180);
auto end = std::upper_bound(timestamps.begin(), timestamps.end(), 320);
std::cout << "Events in range: ";
for (auto it = start; it != end; ++it) {
    std::cout << *it << " ";
}
// Output: 200 250 300

This is the pattern that makes lower_bound/upper_bound worth learning even if you never touch equal_range directly: any “give me everything between A and B” query over sorted data reduces to two binary searches plus a linear walk over just the matching subrange, rather than a linear scan of the whole container with std::copy_if. For a timestamp log with a few hundred entries the difference is meaningless; for a sorted buffer with a few million entries that you query repeatedly — a time-series buffer, an in-memory index — it’s the difference between a lookup that costs microseconds and one that costs milliseconds, and it composes: you can chain another lower_bound/upper_bound pair on the resulting subrange for a second, finer filter, as long as that subrange is sorted by whatever the second filter cares about.

Insert maintaining sorted order

#include <algorithm>
#include <vector>
std::vector<int> sorted = {1, 3, 5, 7, 9};
int newValue = 6;
auto pos = std::lower_bound(sorted.begin(), sorted.end(), newValue);
sorted.insert(pos, newValue);
// sorted is now {1, 3, 5, 6, 7, 9}

Worth flagging before it becomes a surprise: finding the insertion point here is O(log n), but the insert call itself is O(n) on a std::vector, because every element after pos has to shift one slot to make room. lower_bound doesn’t make vector insertion cheap — it only makes finding where to insert cheap. If this happens often enough that the O(n) shift becomes the bottleneck, that’s a sign you want std::set/std::multiset instead of a manually-sorted std::vector, not a sign that lower_bound is the wrong call.

Finding first/last occurrence

std::vector<int> data = {1, 2, 2, 2, 3, 4};
// First occurrence of 2
auto first = std::lower_bound(data.begin(), data.end(), 2);
// Last occurrence of 2
auto last = std::upper_bound(data.begin(), data.end(), 2);
--last;  // Move back to last 2
std::cout << "First 2 at index: " << std::distance(data.begin(), first) << "\n";  // 1
std::cout << "Last 2 at index: " << std::distance(data.begin(), last) << "\n";    // 3

Notice the --last line: upper_bound returns the position after the last matching element, so to get an iterator that points at the last 2, you have to decrement it — and that decrement is only safe because we already confirmed at least one 2 exists (we found first first). Do the same decrement on a range where the value isn’t present at all and you’ll walk one element to the left of wherever upper_bound landed, silently pointing at an unrelated element instead of failing loudly. This exact bookkeeping is what equal_range exists to save you from: std::equal_range(data.begin(), data.end(), 2) returns [first, last) directly, with no manual decrement and no risk of mishandling the empty-range edge case.

Performance comparison

Work per search (1M sorted elements, 10K searches):

Algorithm	Comparisons per search	Notes
`std::find`	up to 1,000,000 (about half on average for a present key)	Linear scan, but sequential and prefetch-friendly
`std::binary_search`	about 20 (log₂ 1M)	O(log n)
`std::lower_bound`	about 20	O(log n)
`std::upper_bound`	about 20	O(log n)
`std::equal_range`	about 40	Two binary searches

Key insight: over 10K searches that is billions of comparisons for std::find versus a few hundred thousand for the binary search family, so binary search wins by orders of magnitude on large sorted data.

Take that comparison as directional, not gospel — the measured gap depends heavily on where the target sits and on cache behavior, and it collapses at the other end of the size spectrum. For a range of ten or twenty elements, a linear scan touching consecutive cache lines can easily beat binary search’s first few probes, which jump to essentially random locations in memory and each risk a cache miss; on genuinely small ranges the two are close enough that readability, not micro-benchmarks, should decide. It’s also worth remembering that the binary search family only pays off with random-access iterators — on std::vector, std::deque, and plain arrays jumping to the midpoint is O(1). The algorithms do compile with std::list or std::forward_list iterators, but advancing to the midpoint is then linear, so the total work is O(n) steps even though comparisons stay O(log n). If your data lives in a linked structure, std::find (or restructuring the data into something contiguous) is the practical option in the standard library — there’s no fast linked-list binary search hiding in <algorithm>.

Common mistakes

Mistake 1: Binary search on unsorted data

std::vector<int> unsorted = {5, 2, 8, 1, 9};
// ❌ Undefined behavior!
bool found = std::binary_search(unsorted.begin(), unsorted.end(), 5);
// ✅ Sort first
std::sort(unsorted.begin(), unsorted.end());
bool found = std::binary_search(unsorted.begin(), unsorted.end(), 5);

The comment “Undefined behavior” undersells how quietly this fails. binary_search doesn’t validate its precondition — there’s no debug assertion in a typical release build, no exception, nothing. It just starts probing the midpoint, then a quarter or three-quarters point, based on comparisons that no longer correspond to a monotonic order, and it can return true for a value that isn’t there, false for a value that is, or, in a pathological case, walk outside the valid range. Worse, it can appear to “work” during testing if the test data happens to be sorted, or the target happens to sit near wherever the algorithm’s probe path lands, and then fail only in production on a differently-shaped input. Treating “the range must be sorted” as a load-bearing invariant — enforced by how the data gets built in the first place, not just remembered by whoever writes the search call — matters more than it looks like it should for a one-line precondition.

Mistake 2: Not checking iterator validity

std::vector<int> data = {1, 2, 3};
auto it = std::find(data.begin(), data.end(), 5);
// ❌ Dereferencing end()
std::cout << *it << "\n";  // Undefined behavior!
// ✅ Check first
if (it != data.end()) {
    std::cout << *it << "\n";
}

Mistake 3: Using wrong bound

std::vector<int> sorted = {1, 3, 5, 5, 5, 7, 9};
// Want to insert after all 5s
auto it = std::lower_bound(sorted.begin(), sorted.end(), 5);  // ❌ Wrong!
// This gives position of first 5
auto it = std::upper_bound(sorted.begin(), sorted.end(), 5);  // ✅ Correct
// This gives position after last 5

Mistake 4: Iterator invalidation

std::vector<int> data = {1, 2, 3, 4, 5};
auto it = std::find(data.begin(), data.end(), 3);
data.push_back(6);  // May reallocate!
// ❌ it may be invalid now
std::cout << *it << "\n";  // Undefined behavior
// ✅ Store index or re-search
size_t index = std::distance(data.begin(), it);
data.push_back(6);
std::cout << data[index] << "\n";

I’ve been caught by exactly this pattern in code that looked innocent at a glance: a loop found an element with std::find, held onto the iterator across a few more lines, and then — several lines later, in a branch I hadn’t been looking at when I made an unrelated change — called push_back on the same vector before using the iterator again. Nothing crashed immediately. std::vector::push_back only reallocates when it exceeds current capacity, so the bug stayed invisible for small inputs that happened to have spare capacity, and only showed up once a longer-running test case grew the vector past that threshold. At that point the “found” iterator pointed into freed memory, and dereferencing it read garbage instead of crashing outright, which made it look like data corruption somewhere else entirely rather than an iterator lifetime bug. The fix is the one shown here: convert the iterator to an index before doing anything that might touch the container’s capacity, and re-derive the iterator (or just index directly) afterward. The rule I follow now is to never hold an iterator across any call that can mutate the same container — not just the obvious ones like push_back, but insert, erase, and even reserve elsewhere on the same vector — and to just store the index whenever there’s any doubt.

Advanced patterns

Custom comparator

#include <algorithm>
#include <vector>
#include <string>
struct Person {
    std::string name;
    int age;
};
std::vector<Person> people = {
    {"Alice", 25},
    {"Bob", 30},
    {"Charlie", 35}
};
// Sort by age
std::sort(people.begin(), people.end(),
         [](const Person& a, const Person& b) {
             return a.age < b.age;
         });
// Binary search by age (must use same comparator!)
Person target{"", 30};
auto it = std::lower_bound(people.begin(), people.end(), target,
                          [](const Person& a, const Person& b) {
                              return a.age < b.age;
                          });
if (it != people.end() && it->age == 30) {
    std::cout << "Found: " << it->name << "\n";  // Bob
}

The comment “must use same comparator!” is doing a lot of work in three words, and it’s worth unpacking. std::sort and std::lower_bound don’t communicate with each other — nothing ties the comparator you sorted with to the comparator you search with. If they disagree, even in a way that looks harmless, the range is no longer sorted with respect to the comparator you’re searching with, and every guarantee lower_bound relies on evaporates.

I ran into a version of this that cost a frustrating afternoon to track down. A comparator was meant to order records first by a primary key, falling back to a secondary key on ties, and the fallback comparison used a floating-point score field with a small epsilon tolerance — something like std::abs(a.score - b.score) < 0.001 treated as “equal, so compare by name instead.” That tolerance made the comparator intransitive: a could compare equal-to-tolerance with b, and b equal-to-tolerance with c, without a and c being equal, which violates the strict weak ordering that every sort and binary-search algorithm in <algorithm> assumes. std::sort still produced an order — it doesn’t verify the comparator either — but it wasn’t a strict weak ordering, so records within an epsilon-equal band could land in different relative positions depending on the sort’s internal pivot choices. Binary search over that “sorted” range then gave inconsistent answers: searching for a value that was definitely present would sometimes find it and sometimes not, depending on exactly which record I searched for, and unnervingly, depending on the standard library version, since a different introsort pivot strategy changed the outcome. The fix wasn’t a workaround in the search call; it was removing the epsilon tolerance from the comparator entirely and handling approximate-equality logic as a separate, explicit step after an exact-ordering search. The lesson that stuck with me: “looks sorted when I print it” and “is a strict weak ordering” are not the same claim, and only the second one is what lower_bound and binary_search actually require.

Count occurrences in sorted range

std::vector<int> data = {1, 2, 2, 2, 3, 4, 4, 5};
int value = 2;
auto range = std::equal_range(data.begin(), data.end(), value);
size_t count = std::distance(range.first, range.second);
std::cout << "Count of " << value << ": " << count << "\n";  // 3

Closest element

std::vector<int> sorted = {10, 20, 30, 40, 50};
int target = 27;
auto it = std::lower_bound(sorted.begin(), sorted.end(), target);
// Check both it and it-1 for closest
int closest;
if (it == sorted.begin()) {
    closest = *it;
} else if (it == sorted.end()) {
    closest = *(it - 1);
} else {
    int before = *(it - 1);
    int after = *it;
    closest = (target - before < after - target) ? before : after;
}
std::cout << "Closest to " << target << ": " << closest << "\n";  // 30

This “closest element” pattern shows why returning an iterator instead of a bare value matters so much: lower_bound hands you a neighborhood — the element before and the element at-or-after the target — and from there you can implement nearest-match, “next available slot,” or “most recent event before time T” logic entirely with iterator arithmetic, without a second pass over the data. None of that is possible starting from binary_search’s bool return, which is the strongest practical argument for defaulting to lower_bound even when you currently only need a yes/no answer — requirements tend to grow into “and where is it” sooner than expected.

Choosing the right algorithm

The following example demonstrates the concept in mermaid:

flowchart TD
    A[Need to search?]
    B{Data sorted?}
    C{Need position?}
    D[std::find]
    E{Existence only?}
    F[std::binary_search]
    G{Need range?}
    H[std::equal_range]
    I[std::lower_bound]
    
    A --> B
    B -->|No| C
    C -->|No| D
    C -->|Yes| D
    B -->|Yes| E
    E -->|Yes| F
    E -->|No| G
    G -->|Yes| H
    G -->|No| I

Notice that the flowchart collapses to std::find for both branches of “data sorted? No,” regardless of whether you need a position, because there’s no O(log n) option once the data isn’t sorted, and std::find already gives a position (its iterator) as its only output. The one case the diagram doesn’t spell out: if you find yourself asking “is this sorted?” repeatedly over the same growing dataset, that’s usually a sign to change data structures entirely — keep it in a std::set/std::map, or sort once and insert at lower_bound to keep it sorted incrementally — rather than resorting the whole range before every search.

Compiler support

Compiler	find/find_if	Binary search	equal_range
GCC	All versions	All versions	All versions
Clang	All versions	All versions	All versions
MSVC	All versions	All versions	All versions

All three of these algorithms have been part of the standard since C++98, so version support has never been the practical constraint. What has changed across standard revisions is the constraints placed on comparator and iterator types — C++20’s move toward constexpr-friendly <algorithm> contents means older custom iterator types that quietly relied on non-constexpr-compatible behavior can newly fail to compile under -std=c++20 even though the identical code built fine under -std=c++17. If you’re upgrading the standard version of an older codebase that leans on these algorithms with hand-written iterators, that’s a more realistic source of build breakage than any actual gap in binary-search support.

Frequently Asked Questions (FAQ)

Q. Should I use std::lower_bound or the container’s own lower_bound on a std::set or std::map?

A. Always call the member function, such as s.lower_bound(x), on std::set and std::map. The free std::lower_bound works with any forward iterator, but tree iterators are not random access, so advancing them is linear and the whole search degrades to O(n). The member version walks the tree directly in O(log n). The free algorithms are the right tool for sorted vectors, arrays and deques.