C++ Binary Search Using STL Examples: binary_search, lower_bound, upper_bound

C++ binary search using STL examples is a must-know topic for students and beginners who want to search quickly in sorted data. The C++ Standard Template Library (STL) gives you ready-to-use algorithms like std::binary_search, std::lower_bound, std::upper_bound, and std::equal_range. In this guide, you’ll learn when and how to use each one, see simple code examples, understand common mistakes, and get step-by-step help for vectors and arrays.

What is binary search in C++ STL and why use it?

Binary search is an efficient way to check whether a value exists in a sorted range (like a sorted array or std::vector). It repeatedly halves the search space, giving logarithmic comparisons. The STL provides a family of functions:

• std::binary_search: returns true/false (membership check)
• std::lower_bound: returns an iterator to the first element not less than the value
• std::upper_bound: returns an iterator to the first element greater than the value
• std::equal_range: returns a pair of iterators spanning all equal elements

Important: the range must be ordered (partitioned) according to the same comparator you pass to the algorithm. Most beginners just keep the data sorted in ascending order and use the default comparator.

Syntax at a glance

// Headers you usually need
#class="cd-package">include <algorithm>  // binary_search, lower_bound, upper_bound, equal_range
#class="cd-package">include <vector>
#class="cd-package">include <iostream>

// Basic forms
bool exists = std::binary_search(first, last, value);
auto it1 = std::lower_bound(first, last, value);
auto it2 = std::upper_bound(first, last, value);
auto range = std::equal_range(first, last, value); // returns {it_low, it_up}

// With a custom comparator (e.g., descending order)
#class="cd-package">include <functional> // std::greater
bool existsDesc = std::binary_search(first, last, value, std::greater<int>{});
auto it1Desc = std::lower_bound(first, last, value, std::greater<int>{});

Quick start: C++ vector binary search example for beginners

This is a simple, beginner-friendly example using std::binary_search on a sorted std::vector.

#class="cd-package">include <algorithm>
#class="cd-package">include <vector>
#class="cd-package">include <iostream>

int main() {
    std::vector<int> v{1, 3, 5, 7, 9, 11}; // sorted ascending

    bool has7 = std::binary_search(v.begin(), v.end(), 7);
    bool has42 = std::binary_search(v.begin(), v.end(), 42);

    std::cout << std::boolalpha;
    std::cout << "Has 7? " << has7 << 'n';
    std::cout << "Has 42? " << has42 << 'n';
    return 0;
}

Has 7? true
Has 42? false

How to use std::binary_search with vector in C++ (and when to use others)

Use std::binary_search for a quick Yes/No. If you need the position (index/iterator), use std::lower_bound or std::upper_bound instead. The following example shows lower_bound and upper_bound for duplicates.

C++ lower_bound and upper_bound examples

#class="cd-package">include <algorithm>
#class="cd-package">include <vector>
#class="cd-package">include <iostream>

int main() {
    std::vector<int> v{10, 20, 20, 20, 30, 40}; // sorted ascending

    auto lb = std::lower_bound(v.begin(), v.end(), 20); // first 20
    auto ub = std::upper_bound(v.begin(), v.end(), 20); // past last 20

    std::size_t first = std::distance(v.begin(), lb);
    std::size_t after_last = std::distance(v.begin(), ub);
    std::size_t count = after_last - first;

    std::cout << "First 20 at index: " << first << 'n';
    std::cout << "One-past-last 20 at index: " << after_last << 'n';
    std::cout << "Count of 20s: " << count << 'n';
    return 0;
}

First 20 at index: 1
One-past-last 20 at index: 4
Count of 20s: 3

Find index of element using lower_bound in C++ for beginners

You can get the index and also tell whether the value exists or where to insert it if it doesn’t.

#class="cd-package">include <algorithm>
#class="cd-package">include <vector>
#class="cd-package">include <iostream>

int main() {
    std::vector<int> v{2, 4, 6, 8, 10}; // sorted
    int x = 7;

    auto it = std::lower_bound(v.begin(), v.end(), x);
    std::size_t pos = std::distance(v.begin(), it);

    if (it != v.end() && *it == x) {
        std::cout << x << " found at index " << pos << 'n';
    } else {
        std::cout << x << " not found; can be inserted at index " << pos << 'n';
    }
    return 0;
}

7 not found; can be inserted at index 3

Insert while keeping the vector sorted (using lower_bound)

This is a classic pattern for maintaining a sorted vector.

#class="cd-package">include <algorithm>
#class="cd-package">include <vector>
#class="cd-package">include <iostream>

int main() {
    std::vector<int> v{1, 3, 5, 9}; // sorted
    int x = 7;

    auto it = std::lower_bound(v.begin(), v.end(), x);
    v.insert(it, x); // keeps v sorted

    std::cout << "After insert: ";
    for (int n : v) std::cout << n << ' ';
    std::cout << 'n';
    return 0;
}

After insert: 1 3 5 7 9

Handling duplicates: std::equal_range

If you need the whole subrange of duplicates in one call, use std::equal_range. It’s equivalent to making both lower_bound and upper_bound calls.

#class="cd-package">include <algorithm>
#class="cd-package">include <vector>
#class="cd-package">include <iostream>

int main() {
    std::vector<int> v{1, 2, 2, 2, 3, 4}; // sorted

    auto range = std::equal_range(v.begin(), v.end(), 2);
    std::size_t first = std::distance(v.begin(), range.first);
    std::size_t after_last = std::distance(v.begin(), range.second);
    std::size_t count = after_last - first;

    std::cout << "2s are in [" << first << ", " << after_last << ") count=" << count << 'n';
    return 0;
}

2s are in [1, 4) count=3

Searching with a custom comparator (descending order)

Binary search works with any ordering as long as the range is partitioned with respect to the same comparator. For descending order, sort descending and use std::greater<> consistently.

#class="cd-package">include <algorithm>
#class="cd-package">include <functional> // std::greater
#class="cd-package">include <vector>
#class="cd-package">include <iostream>

int main() {
    std::vector<int> v{50, 40, 30, 20, 10}; // sorted descending

    bool has30 = std::binary_search(v.begin(), v.end(), 30, std::greater<int>{});
    auto it = std::lower_bound(v.begin(), v.end(), 25, std::greater<int>{});

    std::size_t pos = std::distance(v.begin(), it);
    std::cout << std::boolalpha << "Has 30? " << has30 << 'n';
    std::cout << "Insert 25 at index " << pos << " to keep descending ordern";
    return 0;
}

Has 30? true
Insert 25 at index 3 to keep descending order

Step by step C++ binary search example with STL on custom types

You can store structs and still search by a field. Sort with a comparator that compares the field, and search using a value of the same type (or a constructed value with that field filled).

#class="cd-package">include <algorithm>
#class="cd-package">include <vector>
#class="cd-package">include <string>
#class="cd-package">include <iostream>

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

int main() {
    std::vector<Person> people = {
        {"Alice", 60}, {"Bob", 75}, {"Carol", 75}, {"Dave", 90}
    };

    // Already sorted by score ascending in this example
    // Comparator compares by ___CDPHSTR4___ only
    auto comp = [](const Person& a, const Person& b){ return a.score < b.score; };

    // Find first Person with score >= 75 using lower_bound
    Person key{"", 75};
    auto it = std::lower_bound(people.begin(), people.end(), key, comp);

    if (it != people.end() && it->score == 75) {
        std::cout << "First with score 75: " << it->name << 'n';
    } else {
        std::cout << "No exact score 75. Insert position index: "
                  << std::distance(people.begin(), it) << 'n';
    }

    return 0;
}

First with score 75: Bob

Common mistakes when using binary_search in C++ and how to fix them

• Using it on unsorted data: Undefined behavior. Always sort first with the same comparator you will use for searching.
• Expecting an index from std::binary_search: It returns bool. Use std::lower_bound to get an iterator and convert to index with std::distance.
• Mixing comparators: If you sort descending but search with the default comparator (ascending), results are invalid. Use the exact same comparator.
• Forgetting duplicates: If duplicates matter, use lower_bound/upper_bound or equal_range to get the full subrange.
• Using these algorithms on non-random-access containers: They still do logarithmic comparisons, but advancing iterators may be linear in distance. For std::set/std::map, prefer their member functions lower_bound/upper_bound/equal_range.

Do I need C++20? A quick note on ranges

Since C++20, there are ranges versions like std::ranges::binary_search that work directly with containers and support projections. They are convenient but optional for beginners.

#class="cd-package">include <algorithm> // ranges algorithms
#class="cd-package">include <ranges>
#class="cd-package">include <vector>
#class="cd-package">include <iostream>

int main() {
    std::vector<int> v{1, 3, 5, 7, 9};
    bool ok = std::ranges::binary_search(v, 5); // C++20
    std::cout << std::boolalpha << "Found 5? " << ok << 'n';
    return 0;
}

Found 5? true

Performance and best practices

• Keep arrays or vectors sorted once, then reuse lower_bound/upper_bound for fast queries and insertions.
• For many insertions and lookups, a balanced tree (std::set/std::map) may be simpler; use their member lower_bound/upper_bound/equal_range.
• Comparisons are logarithmic in the number of elements; on non-random-access iterators, moving to the returned position can take linear time. That’s why vectors and arrays are a great fit.
• Always use the same strict-weak-order comparator for sorting and searching (e.g., std::less for ascending, std::greater for descending).

FAQ: People also ask

What is binary search in C++ and when should I use it?

It’s an efficient way to search in a sorted range by repeatedly halving the search interval. Use it when your data is sorted (or can be kept sorted) and you need fast lookups and positions (e.g., membership checks, insertion points, counting duplicates).

How do I use std::binary_search with a vector in C++?

Include <algorithm> and pass v.begin(), v.end(), and the value. It returns a bool. For example: std::binary_search(v.begin(), v.end(), 42). If you need an index, switch to std::lower_bound and use std::distance to compute it.

What is the difference between binary_search, lower_bound, and upper_bound in C++?

binary_search answers Yes/No (bool). lower_bound gives the first position where the value can go (first element not less than value). upper_bound gives the first position after the last equal value. Use equal_range if you want both bounds at once.

Does std::binary_search work on unsorted arrays in C++?

No. The range must be ordered (partitioned) according to the comparator. Using it on an unsorted range is undefined behavior and can produce incorrect results.

How can I get the position of an element using lower_bound in C++?

auto it = std::lower_bound(v.begin(), v.end(), x); then size_t idx = std::distance(v.begin(), it). If it != v.end() and *it == x, the element exists at idx; otherwise idx is the insertion position.

Bonus: Using container member functions

For tree-based containers (std::set, std::map, std::multiset, std::multimap), prefer their member functions over generic algorithms.

#class="cd-package">include <set>
#class="cd-package">include <iostream>

int main() {
    std::set<int> s{1, 3, 5, 7};
    auto it = s.lower_bound(4); // first element >= 4
    if (it != s.end()) std::cout << *it << 'n'; // prints 5
    return 0;
}

5

Where to go next?

Now that you’ve seen how to use std::binary_search, lower_bound, upper_bound, and equal_range, try them on your own practice problems. For more beginner-friendly C++ topics, visit our C++ section: CodDesire C++ Tutorials.

Sources / Further reading

• std::binary_search – cppreference: https://en.cppreference.com/w/cpp/algorithm/binary_search
• std::lower_bound – cppreference: https://en.cppreference.com/w/cpp/algorithm/lower_bound
• std::upper_bound – cppreference: https://en.cppreference.com/w/cpp/algorithm/upper_bound
• std::equal_range – cppreference: https://en.cppreference.com/w/cpp/algorithm/equal_range
• Ranges algorithms (C++20) – cppreference: https://en.cppreference.com/w/cpp/algorithm/ranges
• Algorithm functions – Microsoft Learn: https://learn.microsoft.com/en-us/cpp/standard-library/algorithm-functions?view=msvc-170

Summary

In this binary_search in C++ STL tutorial, you learned how to use std::binary_search for membership, std::lower_bound and std::upper_bound for positions and duplicates, and std::equal_range for the full duplicate span. Remember: keep your range sorted with the same comparator, use lower_bound to find or insert, and prefer container member functions for associative containers. With these C++ binary search using STL examples, you can search and maintain ordered data confidently in your school or college programming projects.