Binary Search

Overview

All four classic algorithms (C++98) require the range to be sorted with respect to the same ordering you pass to the search. More precisely, the range must be partitioned with respect to elem < value (or comp(elem, value)). Searching an unsorted range is undefined behavior, not just a wrong answer.

Key properties:

• Equivalence, not equality. Only operator< (or your comparator) is used. Two values are equivalent if neither is less than the other.
• Comparisons are O(log N) for any forward iterator. The iterator traversal is O(log N) only for random-access iterators; on std::list or std::forward_list it is O(N) steps, so a linear find is usually just as good.
• No parallel overloads. None of these accept an execution policy (C++17 parallelism does not apply).
• constexpr since C++20. All of them can be used in constant expressions.
• Ranges versions since C++20 live in std::ranges and support projections.

binary_search only answers yes/no. In practice lower_bound is the workhorse: it gives you the position, which serves lookup, insertion point, and range-boundary queries.

Syntax

#include <algorithm>

// Classic (C++98), constexpr since C++20
template<class It, class T>
bool binary_search(It first, It last, const T& value);

template<class It, class T, class Compare>
bool binary_search(It first, It last, const T& value, Compare comp);

template<class It, class T>
It lower_bound(It first, It last, const T& value);

template<class It, class T>
It upper_bound(It first, It last, const T& value);

template<class It, class T>
std::pair<It, It> equal_range(It first, It last, const T& value);

// C++11
template<class It, class Pred>
It partition_point(It first, It last, Pred pred);

// C++20 ranges: projections, range overloads, return std::ranges::subrange for equal_range
std::ranges::lower_bound(range, value, comp, proj);

Comparator argument order matters and is asymmetric:

• lower_bound calls comp(element, value)
• upper_bound calls comp(value, element)
• equal_range and binary_search may call both orders

A comparator that accepts (const T&, const T&) hides this; a heterogeneous one (key vs. record) must handle both.

Examples

Membership, bounds and counting duplicates

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 3, 3, 3, 5, 8, 13};   // must be sorted

    bool has5 = std::binary_search(v.begin(), v.end(), 5);   // true

    auto lo = std::lower_bound(v.begin(), v.end(), 3);        // -> first 3
    auto hi = std::upper_bound(v.begin(), v.end(), 3);        // -> 5
    std::cout << (lo - v.begin()) << ' ' << (hi - v.begin()); // 1 4

    auto [first, last] = std::equal_range(v.begin(), v.end(), 3); // C++17 structured bindings
    std::cout << "\ncount of 3: " << std::distance(first, last); // 3
}

Sorted insertion (keeping a vector ordered)

#include <algorithm>
#include <vector>

template<class T>
void insert_sorted(std::vector<T>& v, T value) {
    auto pos = std::upper_bound(v.begin(), v.end(), value); // stable: after equal elements
    v.insert(pos, std::move(value));
}

Using upper_bound places new items after existing equivalents, preserving insertion order among equals. Use lower_bound to insert before them.

Searching records by key with a heterogeneous comparator

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

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

const Employee* find_by_id(const std::vector<Employee>& sorted_by_id, int id) {
    auto it = std::lower_bound(
        sorted_by_id.begin(), sorted_by_id.end(), id,
        [](const Employee& e, int key) { return e.id < key; }); // comp(element, value)
    return (it != sorted_by_id.end() && it->id == id) ? &*it : nullptr;
}

Note the two-step pattern: lower_bound finds a candidate, then you verify equivalence. lower_bound returns the insertion point, not a guaranteed match.

Ranges with projections (C++20)

#include <algorithm>   // C++20 std::ranges
#include <vector>

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

const Employee* find_by_id20(const std::vector<Employee>& v, int id) {
    auto it = std::ranges::lower_bound(v, id, {}, &Employee::id); // C++20: projection
    return (it != v.end() && it->id == id) ? &*it : nullptr;
}

The projection removes the need for a custom lambda and avoids the argument-order trap.

partition_point for predicate-based search (C++11)

#include <algorithm>
#include <vector>

// Data is sorted by latency; find first sample exceeding the SLA
std::vector<double> latencies_ms{0.4, 0.9, 1.2, 4.8, 12.0};
auto it = std::partition_point(latencies_ms.begin(), latencies_ms.end(),
                               [](double x) { return x <= 5.0; });
// it -> 12.0

Use this when there is no concrete value to compare against, only a monotone predicate (true…true, false…false).

Associative containers: prefer the members

#include <set>

std::set<int> s{1, 3, 5, 7};
auto it = s.lower_bound(4);   // member: O(log N), uses tree structure
// std::lower_bound(s.begin(), s.end(), 4) is O(N) iterator steps on a bidirectional iterator

std::set, std::map, std::multiset and std::multimap provide member lower_bound, upper_bound, equal_range. Since C++14, with a transparent comparator (std::less<>), these members accept heterogeneous keys (e.g. std::string_view against std::string keys) without constructing a temporary. Unordered containers have no such members.

Best Practices

• Prefer lower_bound over binary_search whenever you need the element afterwards. Calling binary_search then find does the work twice.
• Use the same comparator for sorting and searching. If the vector was sorted with std::greater<>, search with std::greater<> as well.
• Use equal_range for multi-value ranges rather than two separate calls: it is typically implemented to narrow the search more efficiently.
• Sorted std::vector often beats std::set/std::map for read-heavy lookups thanks to contiguous memory and cache behavior. Sort once, then search many times.
• Use the C++20 ranges overloads and projections when available; they eliminate hand-written comparator lambdas and their ordering mistakes.
• Consider std::span or std::string_view-style views to search sub-ranges without copying.
• Guard dereferences. Always compare against end() before using the result of lower_bound/upper_bound.

Common Pitfalls

• Unsorted input. Behavior is undefined. Add a debug assertion with std::is_sorted (C++11) in tests, not in production hot paths.
• Mismatched ordering. Sorting case-insensitively and searching with default < silently misses elements.
• Treating lower_bound as "find". It returns the first element >= value, which may not equal value. Check equivalence afterwards.
• Wrong comparator argument order. A lambda (const T& value, const Elem& e) passed to lower_bound compiles in some cases and is wrong in others. Remember: lower_bound is (element, value), upper_bound is (value, element).
• Non-strict-weak-ordering comparators. Using <= as comparator violates the requirements and is undefined behavior; use <.
• Floating-point NaN. NaN breaks strict weak ordering, so a range containing NaN is not validly sorted for these algorithms.
• Linked containers. std::lower_bound on std::list does O(N) iterator advances. Use a container member, a sorted vector, or find.
• Iterator invalidation. Inserting using an iterator from lower_bound into a std::vector invalidates other iterators and may reallocate.
• Integer midpoint overflow in hand-rolled searches. (lo + hi) / 2 can overflow; use lo + (hi - lo) / 2, or std::midpoint (C++20, <numeric>). Better still, use the standard algorithms.

See Also

• Merge: combining two sorted ranges
• std::is_sorted, std::sort, std::stable_sort: establishing the precondition
• std::set::lower_bound, std::map::equal_range: container-aware searching