Introduction

A homemade binary search and std::binary_search have the same asymptotic complexity, so the standard library is not magically faster because it uses a different algorithm. When std::binary_search wins in practice, the reasons are usually implementation quality, compiler optimization, or flaws in the benchmark rather than a different big-O story.

Core Sections

Same complexity does not mean same machine code

Both versions should be O(log n), but the exact instructions emitted by the compiler can differ a lot. The standard library implementation is battle-tested, generic in the right way, and often aggressively inlined by the compiler.

A homemade version may accidentally introduce extra bounds checks, signed-versus-unsigned conversions, redundant branches, or iterator arithmetic that the optimizer cannot simplify as well.

A typical manual implementation looks like this:

1bool my_binary_search(const std::vector<int>& values, int target) {
2    int left = 0;
3    int right = static_cast<int>(values.size()) - 1;
4
5    while (left <= right) {
6        int mid = left + (right - left) / 2;
7        if (values[mid] == target) return true;
8        if (values[mid] < target) {
9            left = mid + 1;
10        } else {
11            right = mid - 1;
12        }
13    }
14
15    return false;
16}

This is fine logically, but it is still easy to make it slightly worse than the library version.

std::binary_search benefits from related library machinery

The standard algorithm is implemented in terms of iterator operations and often delegates to lower-level helpers such as std::lower_bound. Those helpers are heavily optimized and widely exercised across compilers and standard library implementations.

1#include <algorithm>
2#include <vector>
3
4bool contains(const std::vector<int>& values, int target) {
5    return std::binary_search(values.begin(), values.end(), target);
6}

That code gives the optimizer a very familiar pattern. The result is often as good as, or better than, ad hoc handwritten code.

Benchmarks are frequently the real problem

A lot of “my code is slower than std::binary_search” results come from weak benchmarking. Common issues include:

• measuring with tiny input sizes where noise dominates
• letting the optimizer remove the search entirely
• timing a one-off call instead of many repeated searches
• benchmarking cache effects instead of the algorithm itself

A minimal benchmark should at least force the result to be used.

1#include <algorithm>
2#include <chrono>
3#include <iostream>
4#include <vector>
5
6int main() {
7    std::vector<int> values;
8    for (int i = 0; i < 1'000'000; ++i) values.push_back(i * 2);
9
10    volatile bool found = false;
11    auto start = std::chrono::high_resolution_clock::now();
12    for (int i = 0; i < 100000; ++i) {
13        found ^= std::binary_search(values.begin(), values.end(), 777777);
14    }
15    auto end = std::chrono::high_resolution_clock::now();
16
17    std::cout << found << '\n';
18    std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << '\n';
19}

Without care like this, the compiler may optimize the whole loop into something misleading.

Homemade implementations often carry subtle costs

Even when the logic is correct, handwritten versions often differ in ways that matter:

• using int where iterator difference types would be safer
• reading values[mid] multiple times instead of caching it once
• creating unpredictable branches
• working on containers or wrappers that inhibit inlining

Sometimes the library version also wins simply because it is easier for the compiler to recognize and optimize as a standard pattern.

The right takeaway

If your handwritten binary search is slower, that does not mean handwritten code is always bad. It means you need evidence before assuming your version is better than the library. In most codebases, the standard algorithm is preferred because it is correct, readable, and already highly optimized.

Common Pitfalls

• Assuming equal big-O complexity guarantees equal real-world speed.
• Comparing implementations with a benchmark the compiler can partially or completely optimize away.
• Writing a correct binary search that still performs extra work because of repeated indexing, conversions, or branches.
• Optimizing the search function before confirming the surrounding data layout and cache behavior are not the actual bottleneck.
• Replacing std::binary_search for speed without first checking whether the standard algorithm is already good enough and clearer.

Summary

• 'std::binary_search and a correct homemade version use the same basic algorithmic idea.'
• Performance differences usually come from code generation, optimization quality, or flawed benchmarking.
• The standard library benefits from mature implementations and compiler familiarity.
• Many homemade versions are slower because of small inefficiencies rather than a fundamentally worse algorithm.
• In production C++, the standard algorithm is usually the right default unless profiling proves otherwise.