std::ranges::lower_bound

From cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
Execution policies (C++17)
Non-modifying sequence operations
(C++11)(C++11)(C++11)
(C++17)
Modifying sequence operations
Partitioning operations
Sorting operations
(C++11)
Binary search operations
Set operations (on sorted ranges)
Heap operations
(C++11)
Minimum/maximum operations
(C++11)
(C++17)

Permutations
Numeric operations
Operations on uninitialized storage
(C++17)
(C++17)
(C++17)
C library
 
Constrained algorithms
Non-modifying sequence operations
Modifying sequence operations
Partitioning operations
Sorting operations
Binary search operations
ranges::lower_bound
Set operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Permutations
Constrained numeric operations
Fold operations
Operations on uninitialized storage
Return types
 
Defined in header <algorithm>
Call signature
template< std::forward_iterator I, std::sentinel_for<I> S,

          class T, class Proj = std::identity,
          std::indirect_strict_weak_order<
              const T*,
              std::projected<I, Proj>> Comp = ranges::less >
constexpr I

lower_bound( I first, S last, const T& value, Comp comp = {}, Proj proj = {} );
(1) (since C++20)
template< ranges::forward_range R, class T, class Proj = std::identity,

          std::indirect_strict_weak_order<
              const T*,
              std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less >
  constexpr ranges::borrowed_iterator_t<R>

lower_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
(2) (since C++20)
1) Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found. The range [first, last) must be partitioned with respect to the expression comp(element, value), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.
2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids, that is:

In practice, they may be implemented as function objects, or with special compiler extensions.

Parameters

first, last - iterator-sentinel pair defining the partially-ordered range to examine
r - the partially-ordered range to examine
value - value to compare the elements to
pred - predicate to apply to the projected elements
proj - projection to apply to the elements

Return value

Iterator pointing to the first element that is not less than value, or last if no such element is found.

Complexity

The number of comparisons and applications of the projection performed are logarithmic in the distance between first and last (At most log
2
(last - first) + O(1)
comparisons and applications of the projection). However, for an iterator that does not model random_access_iterator, the number of iterator increments is linear.

Possible implementation

struct lower_bound_fn {
  template<std::forward_iterator I, std::sentinel_for<I> S,
           class T, class Proj = std::identity,
           std::indirect_strict_weak_order<
               const T*,
               std::projected<I, Proj>> Comp = ranges::less>
  constexpr I operator()( I first, S last, const T& value,
                          Comp comp = {}, Proj proj = {} ) const
  {
      I it;
      std::iter_difference_t<I> count, step;
      count = std::ranges::distance(first, last);
 
      while (count > 0) {
          it = first;
          step = count / 2;
          ranges::advance(it, step, last);
          if (comp(std::invoke(proj, *it), value)) {
              first = ++it;
              count -= step + 1;
          }
          else {
              count = step;
          }
      }
      return first;
  }
 
  template<ranges::forward_range R, class T, class Proj = std::identity,
           std::indirect_strict_weak_order<
               const T*,
               std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less>
  constexpr ranges::borrowed_iterator_t<R>
  operator()( R&& r, const T& value, Comp comp = {}, Proj proj = {} ) const
  {
    return (*this)(ranges::begin(r), ranges::end(r), value,
                   std::ref(comp), std::ref(proj));
  }
};
 
inline constexpr lower_bound_fn lower_bound;

Example

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
namespace ranges = std::ranges;
 
template<std::forward_iterator I, std::sentinel_for<I> S, class T,
         class Proj = std::identity,
         std::indirect_strict_weak_order<
               const T*,
               std::projected<I, Proj>> Comp = ranges::less>
constexpr
I binary_find(I first, S last, const T& value, Comp comp = {}, Proj proj = {})
{
    first = ranges::lower_bound(first, last, value, comp, proj);
    return first != last && !comp(value, proj(*first)) ? first : last;
}
 
int main()
{
    std::vector data = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
 
    auto lower = ranges::lower_bound(data, 4);
    auto upper = ranges::upper_bound(data, 4);
 
    ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
 
    std::cout << '\n';
 
    // classic binary search, returning a value only if it is present
 
    data = { 1, 2, 4, 8, 16 }; 
 
    auto it = binary_find(data.cbegin(), data.cend(), 8); //< choosing '5' will return end()
 
    if(it != data.cend())
        std::cout << *it << " found at index "<< ranges::distance(data.cbegin(), it);
}

Output:

4 4 4 4
8 found at index 3

See also

returns range of elements matching a specific key
(niebloid)
divides a range of elements into two groups
(niebloid)
locates the partition point of a partitioned range
(niebloid)
returns an iterator to the first element greater than a certain value
(niebloid)
returns an iterator to the first element not less than the given value
(function template)