Library

since C++98

Basic

Searching Algorithms

C++ searching algorithms — std::find, binary_search, lower_bound, upper_bound, equal_range, search, and C++20 ranges equivalents with projections.

Searching Algorithmssince C++98

A family of <algorithm> functions for locating elements or subsequences in ranges, spanning O(n) linear scan, O(log n) binary search on partitioned ranges, and O(n+m) pattern matching via pluggable searchers introduced in C++17.

Overview

The standard library organises searching into three tiers:

Linear search — works on any range with any iterator category; O(n).
Binary search — O(log n), but the range must be partitioned on the comparison (sorted order is sufficient, not strictly necessary).
Subsequence/pattern search — locating a sub-range within a range; O(n·m) naively, O(n) average with C++17 searcher objects.

C++20 range algorithms (std::ranges::find, etc.) accept whole range objects and support projections, which replace the manual transform-then-search pattern. C++23 added std::ranges::find_last variants and std::ranges::contains.

Linear Search

`std::find` · `std::find_if` · `std::find_if_not`

std::find uses operator==. std::find_if accepts a unary predicate. std::find_if_not (C++11) finds the first element for which the predicate returns false.

cpp

#include <algorithm>
#include <vector>

std::vector<int> v{4, 1, 3, 7, 2};

// C++98
auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end())
    std::println("found {} at index {}", *it, std::distance(v.begin(), it));

// C++98: first element satisfying predicate
auto gt5 = std::find_if(v.begin(), v.end(), [](int x){ return x > 5; });

// C++11: first element failing predicate (first non-positive here)
auto nonpos = std::find_if_not(v.begin(), v.end(), [](int x){ return x > 0; });

All three return end() on failure — always check before dereferencing.

`std::ranges::find_last` variants (C++23)

The non-ranges standard library has no find_last. C++23 added range-based versions that scan for the last match. They return a std::ranges::subrange, not a single iterator.

cpp

#include <algorithm>

std::vector<int> v{4, 1, 3, 7, 2, 6};

// C++23 — ranges only
auto r = std::ranges::find_last_if(v, [](int x){ return x < 5; });
if (!r.empty())
    std::println("last element < 5: {}", *r.begin());  // 2

`std::adjacent_find`

Finds the first consecutive pair satisfying equality or a binary predicate. Useful for detecting duplicate runs or verifying sortedness before a binary search.

cpp

std::vector<int> v{1, 3, 3, 5, 7};

// C++98: consecutive equal elements
auto dup = std::adjacent_find(v.begin(), v.end());
// *dup == 3, *(dup+1) == 3

// Detect first out-of-order transition
auto bad = std::adjacent_find(v.begin(), v.end(),
    [](int a, int b){ return b < a; });
// bad == v.end() → range is non-decreasing

`std::count` / `std::count_if`

cpp

std::vector<int> v{1, 2, 2, 3, 2, 4};
auto twos = std::count(v.begin(), v.end(), 2);                              // 3
auto even = std::count_if(v.begin(), v.end(), [](int x){ return !(x%2); }); // 4

Prefer member count() on associative containers — std::count on std::map or std::set is O(n) and ignores tree structure.

Binary Search on Partitioned Ranges

All four algorithms require the range to be partitioned on the comparison: for some threshold, all elements for which comp(e, value) is true come before all elements for which it is false. Sorted order satisfies this. Calling these on an unpartitioned range is undefined behaviour — no diagnostic is required.

On random-access iterators the algorithms perform O(log n) comparisons and O(log n) advances. On forward iterators they still perform O(log n) comparisons but O(n) iterator advances — the log-n win is only in comparison count.

`std::binary_search` — existence check

Returns bool. Does not return an iterator. If you also need the position, call lower_bound directly.

cpp

std::vector<int> sorted{1, 3, 5, 7, 9, 11};

bool found5 = std::binary_search(sorted.begin(), sorted.end(), 5);  // true
bool found6 = std::binary_search(sorted.begin(), sorted.end(), 6);  // false

// Custom comparator — must match the ordering used to sort
struct Event { int timestamp; std::string name; };
std::vector<Event> log = /* sorted by timestamp */ {};
bool hit = std::binary_search(log.begin(), log.end(), Event{1700000000, {}},
    [](const Event& a, const Event& b){ return a.timestamp < b.timestamp; });

`std::lower_bound` — first position ≥ value

Returns an iterator to the first element e for which !(e < value) (or !comp(e, value)) holds. This is the canonical sorted-insertion point.

cpp

std::vector<int> v{1, 3, 5, 5, 5, 7, 9};

auto lo = std::lower_bound(v.begin(), v.end(), 5);
// *lo == 5, index 2

// Test presence without a second binary search
bool present = (lo != v.end() && *lo == 5);

// Sorted insertion — O(log n) search, O(n) shift for std::vector
auto pos = std::lower_bound(v.begin(), v.end(), 6);
v.insert(pos, 6);  // {1,3,5,5,5,6,7,9}

`std::upper_bound` — first position > value

Returns an iterator past the last element equal to value; combined with lower_bound, this gives the contiguous range of equal elements.

cpp

std::vector<int> v{1, 3, 5, 5, 5, 7, 9};

auto lo = std::lower_bound(v.begin(), v.end(), 5);
auto hi = std::upper_bound(v.begin(), v.end(), 5);
// *hi == 7; hi - lo == 3 (number of 5s)

`std::equal_range` — both bounds at once

Performs two binary searches internally and returns a std::pair of iterators. Prefer this over separate lower_bound + upper_bound calls when you need both.

cpp

std::vector<int> v{1, 3, 5, 5, 5, 7, 9};

auto [lo, hi] = std::equal_range(v.begin(), v.end(), 5);
bool present = lo != hi;
int  count   = static_cast<int>(hi - lo);  // 3 — random-access only

// For bidirectional/forward iterators:
auto count_fwd = static_cast<int>(std::distance(lo, hi));

Subsequence and Pattern Search

`std::search` with pluggable searchers

std::search finds the first occurrence of a sub-range. C++17 added searcher objects that separate table construction from searching, enabling efficient reuse across multiple texts.

cpp

#include <algorithm>
#include <functional>  // C++17 searchers

std::string text    = "the quick brown fox jumps over the lazy fox";
std::string pattern = "fox";

// C++98: naive O(n·m)
auto it = std::search(text.begin(), text.end(),
                      pattern.begin(), pattern.end());

// C++17: Boyer-Moore — bad-character + good-suffix tables
// O(n/m) best case, O(n) average; worst case O(n·m) for adversarial input
auto bm = std::boyer_moore_searcher(pattern.begin(), pattern.end());
it = std::search(text.begin(), text.end(), bm);

// C++17: Boyer-Moore-Horspool — simpler tables, lower construction cost,
// similar average-case performance
auto bmh = std::boyer_moore_horspool_searcher(pattern.begin(), pattern.end());
it = std::search(text.begin(), text.end(), bmh);

// Build searcher once, search many texts
std::vector<std::string> corpus = /* ... */ {};
for (const auto& doc : corpus) {
    auto pos = std::search(doc.begin(), doc.end(), bm);
    if (pos != doc.end())
        std::println("match in doc at {}", std::distance(doc.begin(), pos));
}

std::default_searcher (C++17) wraps the naive algorithm — useful for generic code that accepts any searcher type.

`std::find_end` — last occurrence of a subrange

cpp

std::vector<int> haystack{1, 2, 3, 4, 1, 2, 5};
std::vector<int> needle{1, 2};

// C++98: O(n·m), returns iterator to start of last occurrence
auto it = std::find_end(haystack.begin(), haystack.end(),
                        needle.begin(), needle.end());
// it points to index 4 (the second {1,2})

`std::find_first_of`

Finds the first element in [first1, last1) that matches any element in [first2, last2):

cpp

std::string text   = "the quick brown fox";
std::string vowels = "aeiou";

auto it = std::find_first_of(text.begin(), text.end(),
                              vowels.begin(), vowels.end());
// *it == 'e'

C++20 Ranges

Range algorithms accept whole containers, return borrowed_iterator_t (safe after the container's lifetime ends inside a pipeline), and support projections — a function applied to each element before comparison:

cpp

#include <algorithm>
#include <ranges>

std::vector<int> v{1, 3, 5, 7, 9};

auto it            = std::ranges::find(v, 5);              // C++20
bool ok            = std::ranges::binary_search(v, 5);     // C++20
auto lo            = std::ranges::lower_bound(v, 5);       // C++20
auto [lo2, hi2]    = std::ranges::equal_range(v, 5);       // C++20

// Projection: binary-search a struct by a member without a comparator lambda
struct Item { std::string name; int score; };
std::vector<Item> items = /* sorted by score */ {};

auto it2   = std::ranges::lower_bound(items, 42, {}, &Item::score);  // C++20
bool found = it2 != items.end() && it2->score == 42;

// C++23: ranges::contains replaces the lower_bound + value-check pattern
bool has42 = std::ranges::contains(items, 42, &Item::score);  // C++23

Projection support eliminates the need for custom comparators in many common cases and is only available on std::ranges:: algorithms, not the classic iterator-pair overloads.

Best Practices

Use lower_bound when you need a position, not binary_search. binary_search returns only bool. If you call binary_search and then lower_bound, you pay two O(log n) traversals. Call lower_bound once and check it != end && *it == value.

Use member find on associative containers. std::find on std::map, std::set, or std::unordered_map is O(n) — it scans linearly and ignores the tree or hash table. Always prefer container.find(key).

Build searcher objects outside search loops. std::boyer_moore_searcher constructs lookup tables on construction. Constructing it inside a loop over a corpus makes every call O(m) just in setup cost.

Match comparators between sort and search. The comparator passed to lower_bound or equal_range must induce the same partial order used to sort the range. Mixing comparators violates the partitioned invariant and causes undefined behaviour.

Use std::ranges::contains (C++23) for simple membership tests on sorted ranges with projections — it reads more clearly than lower_bound + dereference + compare.

Common Pitfalls

Calling binary search algorithms on unsorted input. The standard requires the range be partitioned; the algorithms will not diagnose violations and may return nonsense or loop. Use std::is_sorted during development to assert the precondition.

Off-by-one with lower_bound vs upper_bound. lower_bound returns the first position not less than the value; if you want the slot after all equal elements (e.g. to insert after duplicates), use upper_bound.

find_last_if return type (C++23). Unlike find_if, std::ranges::find_last_if returns a std::ranges::subrange. Accessing it as a single iterator is a compile error; use .begin() to get the matching iterator, and check .empty() for the not-found case.

equal_range distance on non-random-access iterators. hi - lo only compiles for random-access iterators. Use std::distance(lo, hi) for bidirectional or forward iterators — but note this is O(n).

std::search complexity. The default overload uses a naive algorithm. For pattern length m > ~8 and large corpora, construct a boyer_moore_searcher once and reuse it.

Performance Summary

Algorithm	Complexity	Prerequisite
`find` / `find_if` / `find_if_not`	O(n)	None
`count` / `count_if`	O(n)	None
`adjacent_find`	O(n)	None
`find_end` / `find_first_of`	O(n·m)	None
`search` (default)	O(n·m)	None
`search` (Boyer-Moore, C++17)	O(n) avg	None (C++17)
`binary_search`	O(log n)	Partitioned range
`lower_bound` / `upper_bound`	O(log n)	Partitioned range
`equal_range`	O(log n)	Partitioned range

O(log n) comparisons apply universally; O(log n) iterator advances only for random-access iterators.

Binary search: lower_bound, upper_bound, equal_range

The three binary-search position algorithms cover every lookup pattern on sorted data. lower_bound gives the insertion point; upper_bound gives the slot after all equal elements; equal_range returns both in one call.

cpp

#include <algorithm>
#include <vector>

std::vector<int> v{1, 2, 4, 4, 4, 6, 8};

// C++98: first position not-less-than 4
auto lo = std::lower_bound(v.begin(), v.end(), 4); // index 2

// C++98: first position greater-than 4
auto hi = std::upper_bound(v.begin(), v.end(), 4); // index 5

// Count duplicates without two separate calls
auto [lo2, hi2] = std::equal_range(v.begin(), v.end(), 4); // C++11 structured binding
int n = static_cast<int>(hi2 - lo2); // 3

// Sorted insertion preserving order — O(log n) search + O(n) shift
auto pos = std::upper_bound(v.begin(), v.end(), 4);
v.insert(pos, 4); // inserts after existing 4s

Use lower_bound when inserting before duplicates and upper_bound when inserting after them — the choice matters for stable-sort semantics on custom types.

Searching with projections (C++20 ranges)

C++20 range algorithms accept a projection that transforms each element before comparison, eliminating most hand-written comparator lambdas. A projection is any callable — pointer-to-member, lambda, or function pointer — applied to both sides of every comparison.

cpp

#include <algorithm>
#include <ranges>
#include <string>
#include <vector>

struct Employee {
    std::string name;
    int         id;
    double      salary;
};

// C++20: sorted by id, search by id using a member pointer
std::vector<Employee> staff = /* sorted by id */ {};

auto it = std::ranges::lower_bound(staff, 1042, {}, &Employee::id); // C++20
if (it != staff.end() && it->id == 1042)
    std::println("found: {}", it->name);

// C++20: search by salary with a lambda projection
auto rich = std::ranges::find_if(staff,
    [](double s){ return s > 100'000.0; },
    &Employee::salary); // C++20

// C++23: cleaner membership test with projection
bool exists = std::ranges::contains(staff, 1042, &Employee::id); // C++23

Projections compose naturally with range views — filter first, then project-search — without constructing temporary containers.

std::search with searcher objects

std::search with C++17 searcher objects separates index construction from searching, making multi-document lookups significantly faster. Build the searcher once per pattern; reuse it across the entire corpus.

cpp

#include <algorithm>
#include <functional>
#include <string>
#include <vector>

std::string pattern = "reinterpret_cast";

// C++17: Boyer-Moore — O(n) average; bad+good suffix tables
auto bm = std::boyer_moore_searcher(pattern.begin(), pattern.end());

// C++17: Boyer-Moore-Horspool — simpler tables, lower build cost
auto bmh = std::boyer_moore_horspool_searcher(pattern.begin(), pattern.end());

std::vector<std::string> files = /* loaded text files */ {};

for (const auto& f : files) {
    // Reuse bm — table construction already paid
    auto pos = std::search(f.begin(), f.end(), bm); // C++17
    while (pos != f.end()) {
        std::println("hit at offset {}", std::distance(f.begin(), pos));
        pos = std::search(std::next(pos), f.end(), bm);
    }
}

// C++17: default_searcher wraps the naive O(n·m) algorithm
// — useful as a drop-in when writing searcher-generic code
auto ds = std::default_searcher(pattern.begin(), pattern.end()); // C++17
auto it = std::search(files[0].begin(), files[0].end(), ds);

Boyer-Moore requires random-access iterators and element types that are hashable (or have a traits_type). Use default_searcher when working with forward iterators only.

Finding adjacent elements

std::adjacent_find locates the first consecutive pair satisfying a condition, making it the standard tool for detecting runs, duplicates, or sortedness violations. Without a predicate it checks equality; with one it evaluates any binary relationship.

cpp

#include <algorithm>
#include <vector>

std::vector<int> v{1, 2, 2, 3, 4, 4, 5};

// C++98: first pair of equal adjacent elements
auto dup = std::adjacent_find(v.begin(), v.end());
if (dup != v.end())
    std::println("first dup: {} at index {}", *dup, std::distance(v.begin(), dup));

// C++98: first descending transition — detect unsorted position
auto bad = std::adjacent_find(v.begin(), v.end(),
    [](int a, int b){ return b < a; });
bool sorted = (bad == v.end()); // true

// Detect integer gaps (non-consecutive values)
auto gap = std::adjacent_find(v.begin(), v.end(),
    [](int a, int b){ return b != a + 1; }); // C++11 lambda

std::adjacent_find returns an iterator to the first element of the matching pair, so *(it+1) gives the second element — always check it != end() before advancing.

Searching in sorted vs unsorted ranges

Choosing the wrong search tier is the most common searching performance bug in C++. Linear search is always safe; binary search is O(log n) but silently produces wrong answers on unsorted input.

cpp

#include <algorithm>
#include <cassert>
#include <vector>

std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};

// Linear — always correct, O(n)
auto it = std::find(v.begin(), v.end(), 5); // C++98

// Sort first, then binary-search — O(n log n) + O(log n)
std::sort(v.begin(), v.end()); // {1,1,2,3,4,5,6,9}
assert(std::is_sorted(v.begin(), v.end())); // precondition check in debug builds
bool found = std::binary_search(v.begin(), v.end(), 5); // C++98

// C++17: assert in a one-liner using is_sorted_until
assert(std::is_sorted_until(v.begin(), v.end()) == v.end());

// Partially sorted: if only [begin, mid) is sorted, restrict binary search
auto mid = v.begin() + 4;
auto lo  = std::lower_bound(v.begin(), mid, 3); // C++98 — only on sorted half

When data arrives nearly sorted, std::is_sorted costs O(n) — run it once in a debug build rather than before every search.

Searching with custom comparators

Every binary-search algorithm accepts a comparator, but it must induce the same strict-weak order that was used to sort the range. Mixing comparators produces undefined behaviour without any diagnostic.

cpp

#include <algorithm>
#include <vector>
#include <string>

struct Record {
    int         key;
    std::string value;
};

auto by_key = [](const Record& a, const Record& b){ return a.key < b.key; };

std::vector<Record> recs = {/* ... */};
std::sort(recs.begin(), recs.end(), by_key); // C++11

// Pass the same comparator to all binary-search calls
Record probe{42, {}};
bool   found = std::binary_search(recs.begin(), recs.end(), probe, by_key); // C++98
auto   lo    = std::lower_bound  (recs.begin(), recs.end(), probe, by_key); // C++98
auto [lo2, hi2] = std::equal_range(recs.begin(), recs.end(), probe, by_key); // C++11

// C++20 ranges: prefer projections over comparators for single-member keys
auto it = std::ranges::lower_bound(recs, 42, {}, &Record::key); // C++20

Heterogeneous lookup is also possible: the comparator only needs to accept (T, U) and (U, T) pairs, allowing the probe type to differ from the element type — no temporary Record needed.

See Also

Sorting Algorithms — prerequisite for binary search
Partitioning Algorithms — weaker prerequisite sufficient for lower_bound
Ranges — C++20 range adaptors, views, and projected algorithms
Associative Containers — O(log n) member find for std::map/std::set