std::ranges::lower_bound

< cpp‎ | algorithm‎ | ranges
 
C++
 
算法库
有制约算法及范围上的算法 (C++20)
有制约算法： std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
(C++11)
二分搜索操作
集合操作（在已排序范围上）
堆操作
(C++11)
(C++11)
最小/最大操作
(C++11)
(C++11)
(C++17)

排列
数值运算
C 库
 
有制约算法
不修改序列的操作
修改序列的操作
未初始化存储上的操作
划分操作
排序操作
二分搜索操作
ranges::lower_bound
集合操作（在已排序范围上）
堆操作
最小/最大操作
排列
 
定义于头文件 <algorithm>
调用签名
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) (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) (C++20 起)
1) 返回指向范围 [first, last) 中首个不小于（即大于或等于） value 的元素的迭代器，或若找不到这种元素返回 last 。 范围 [first, last) 必须已按照表达式 comp(element, value) 划分，即所有该表达式对其为 true 的元素必须前趋所有该表达式对其为 false 的元素。完全排序的范围符合此判别标准。
2) 同 (1) ，但以 r 为源范围，如同以 ranges::begin(r) 为 first 并以 ranges::end(r) 为 last 。

此页面上描述的仿函数实体是 niebloid ，即：

实际上，它们能以函数对象，或以某些特殊编译器扩展实现。

参数

first, last - 定义要检验的部分有序范围的迭代器-哨位对
r - 要检验的部分有序范围
value - 要与元素比较的值
pred - 应用到投影后元素的谓词
proj - 应用到元素的投影

返回值

指向首个不小于 value 的元素的迭代器，或若找不到这种元素则为 last 。

复杂度

比较和应用投影的次数与 first 和 last 之间的距离成对数（至多比较和应用投影 log
2(last - first) + O(1) 次）。然而，对于不实现 random_access_iterator 的迭代器，迭代器自增次数为线性。

可能的实现

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(*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;

示例

运行此代码
#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>
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, *first) ? first : last;
}
 
int main()
{
    std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
 
    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';
 
    // 经典二分搜索，仅若存在才返回值
 
    data = { 1, 2, 4, 6, 9, 10 }; 
 
    auto it = binary_find(data.cbegin(), data.cend(), 4); //< 选择 '5' 将返回 end()
 
    if(it != data.cend())
      std::cout << *it << " found at index "<< ranges::distance(data.cbegin(), it);
 
    return 0;
}

输出： 

4 4 4 
4 found at index 2

参阅

(C++20)
 返回匹配特定值的元素范围
(niebloid)
(C++20)
 将范围中的元素分为二组
(niebloid)
(C++20)
 定位已划分范围的划分点
(niebloid)
(C++20)
 返回指向首个大于某值的元素的迭代器
(niebloid)
返回指向第一个不小于给定值的元素的迭代器
(函数模板)