C++ STL Binary Search

Use std::binary_search when you need to know whether a value occurs in an ordered range. It returns a Boolean membership result; it does not return the matching iterator or the number of matching values. The function is useful for a vector, array, or another range with suitable iterators, provided the ordering requirements are met.

Understand the requirements of std::binary_search

The searched range must be partitioned according to the comparison used by the search. In ordinary use, this means the elements are sorted in ascending order with the same ordering as the default comparison. If the range is not ordered that way, the result is not a reliable membership answer. Sorting once and then changing or partially modifying elements can also invalidate the precondition.

The iterator pair describes a half-open range, [first, last): first points to the first element considered, while last points one past the final element and is excluded. Passing container.begin() and container.end() searches the whole container. An empty range is valid and reports no match; a one-element range includes that element when first points to it and last follows it.

The result is true when an element equivalent under the ordering is present and false otherwise. If you need a position, use an operation such as std::lower_bound and check that its returned iterator is not last and that the value is equivalent. std::binary_search alone cannot identify which duplicate matched.

Use std::binary_search with a sorted range

Include <algorithm> for the function, <iostream> for output, and <vector> for this container. The following complete program checks a value that is present and one that is absent. The text uses the Boolean result directly, so the two outcomes are visible without relying on an iterator.

Run this example:

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

int main() {
    const std::vector<int> values{2, 4, 6, 8, 10};
    const bool has_six = std::binary_search(values.begin(), values.end(), 6);
    const bool has_seven = std::binary_search(values.begin(), values.end(), 7);

    std::cout << std::boolalpha
              << "6 found: " << has_six << '\n'
              << "7 found: " << has_seven << '\n';
}

6 found: true
7 found: false

The vector is already sorted, and its full iterator range is passed to each call. Change either target to adapt the example; keep the vector in the same ordering expected by the search. The function does not sort the range for you.

Search with a custom comparator

For a user-defined type, pass a comparator that defines the ordering used for the range. Sort with that same comparator before searching. In this example, records are ordered by age, and the target is considered present when a record with that age is present. The name is not part of this comparator’s identity rule.

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

struct Person {
    std::string name;
    int age;
};

int main() {
    const auto by_age = [](const Person& left, const Person& right) {
        return left.age < right.age;
    };

    std::vector<Person> people{{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    std::sort(people.begin(), people.end(), by_age);

    const Person target{"", 25};
    const bool found = std::binary_search(
        people.begin(), people.end(), target, by_age);
    return found ? 0 : 1;
}

The comparator compares values, not iterators. It must provide the ordering used to arrange the range and be compatible with comparisons between the range elements and the target. Here, two records with the same age are equivalent for this search, even if their names differ. If the application needs to distinguish those records, include the distinguishing fields in the ordering or use a different lookup strategy.

Avoid common binary-search mistakes

• Searching unsorted data: sort the range first. Sorting by one key and searching with another ordering does not satisfy the search requirement.
• Treating last as an element: last is excluded. Use container.end() for a whole-container search; do not dereference it.
• Expecting an iterator: the return type is Boolean. Use std::lower_bound when you need a location, then check its result before dereferencing it.
• Using a mismatched comparator: the sort and search must agree on ordering and equivalence. A comparator that treats two records as equivalent answers membership by that rule, not by every field in the record.

These checks make the function’s result meaningful. The library performs the search, but it cannot detect that the range was prepared with a different order or that the comparator does not match the data.