Difference between std::find and std::binarysearch?
C++Level: IntermediateSTL Containers & Iterators
Difference between std::find and std::binary_search?
Hints
- Identify types, object lifetimes and compile-time decisions.
- Separate language guarantees from a particular compiler's behavior.
Answer
Searching
std::find
:Source: src/algorithm/find
std::find performs a linear search through a range, returning an iterator to
the first element that equals the specified value, or end() if not found. The
algorithm has O(n) complexity and works with any input iterator, making it
universally applicable but potentially slow for large unsorted containers. For
sorted containers, prefer std::binary_search, std::lower_bound, or
std::upper_bound which offer O(log n) complexity. For associative containers
like std::set or std::map, use their member find() functions which
are optimized for their internal structure.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector v{1, 2, 3, 4, 5};
auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) {
std::cout << "Found: " << *it << "\n";
}
}
std::find_if and std::find_if_not
:Source: src/algorithm/find-if
std::find_if searches for the first element satisfying a predicate function,
while std::find_if_not finds the first element that does not satisfy the
predicate. These are more flexible than std::find because they allow arbitrary
search conditions rather than simple equality. Common use cases include finding
the first negative number, the first element exceeding a threshold, or the first
invalid entry in a dataset. Both algorithms have O(n) complexity.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector v{1, 2, 3, 4, 5};
auto even = std::find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
auto odd = std::find_if_not(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
std::cout << "First even: " << *even << "\n"; // 2
std::cout << "First odd: " << *odd << "\n"; // 1
}
std::binary_search
:Source: src/algorithm/binary-search
std::binary_search checks whether a value exists in a sorted range using
binary search with O(log n) complexity. It returns a boolean indicating presence
but does not provide the element's position. To get an iterator to the element,
use std::lower_bound (first element >= value) or std::upper_bound (first
element > value). The std::equal_range function returns both bounds as a pair,
defining the range of elements equal to the search value. These functions are
essential for efficient searching and insertion in sorted containers.
#include <algorithm>
#include <vector>
int main() {
std::vector v{1, 2, 3, 4, 5};
bool found = std::binary_search(v.begin(), v.end(), 3);
// lower_bound: first element >= value
auto lb = std::lower_bound(v.begin(), v.end(), 3);
// upper_bound: first element > value
auto ub = std::upper_bound(v.begin(), v.end(), 3);
// equal_range: pair of lower_bound and upper_bound
auto [lo, hi] = std::equal_range(v.begin(), v.end(), 3);
}
Source and licence: C/C++ Interview Cheatsheet — Chang Ning Tsai · MIT