二分查找¶
lower_bound¶
函数原型：
template <class _FwdIt, class _Ty, class _Pr>
void lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Pr _Pred);
用途：在 _First 和 _Last 迭代器之间构成的区域内寻找第一个大于等于 _Val 的元素（不包含 _Last 指向的元素），并返回该元素的迭代器。如果没有该元素，则返回 _Last。
使用之前需排序，查找复杂度 \(\mathcal O(\log_2 n)\)。
upper_bound¶
函数原型：
template <class _FwdIt, class _Ty, class _Pr>
void upper_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Pr _Pred);
用途：在 _First 和 _Last 迭代器之间构成的区域内寻找第一个大于 _Val 的元素（不包含 _Last 指向的元素），并返回该元素的迭代器。如果没有该元素，则返回 _Last。
使用之前需排序，查找复杂度 \(\mathcal O(\log_2 n)\)。