Skip to content
Quantoros

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);
}

Answer section

Source and licence: C/C++ Interview Cheatsheet — Chang Ning Tsai · MIT

Related questions