Sorted Search

In C++, std::binary_search finds whether or not an element is present - it does not return the matching iterator.

template<class ForwardIt, class T>
/* --> */ bool /* <--- */ binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::lower_bound(first, last, value);
    return (!(first == last) && !(value < *first));
}

Lower Bound

If you want to find the first position of an element in a sorted container, use std::lower_bound.

auto it = std::lower_bound(hay.begin(), hay.end(), needle);
if (it != hay.end() && !(needle < *it)) {
  Process(*it);
} else {
  // Element not found.
}

Upper Bound

If you want to find the last position of an element in a sorted container, use std::upper_bound.

auto it = std::upper_bound(hay.begin(), hay.end(), needle);
if (it != hay.end()) {
  // *it > needle was found.
} else {
  // No upper bound found:
  // (a) `needle` was the maximum in `hay`, or
  // (b) `needle` was not in `hay`).
}

Equal Range

In the case when you want to find both the lower and upper bounds (for example, all the edges for a node), you can use std::equal_range.

auto [begin, end] = std::equal_range(hay.begin(), hay.end(), needle);
for (auto it = begin; it != end; ++it) {
  Process(*it);
}