/**
* @brief Finds the first position in which @a val could be inserted
* without changing the ordering.
* @param first An iterator.
* @param last Another iterator.
* @param val The search term.
* @return An iterator pointing to the first element <em>not less
* than</em> @a val, or end() if every element is less than
* @a val.
* @ingroup binary_search_algorithms
*/
template<typename _ForwardIterator, typename _Tp>
_ForwardIterator
lower_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
__glibcxx_requires_partitioned_lower(__first, __last, __val);
_DistanceType __len = std::distance(__first, __last);
while (__len > 0)
{
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
if (*__middle < __val)
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else
__len = __half;
}
return __first;
}
/**
* @brief Finds the last position in which @a val could be inserted
* without changing the ordering.
* @ingroup binary_search_algorithms
* @param first An iterator.
* @param last Another iterator.
* @param val The search term.
* @return An iterator pointing to the first element greater than @a val,
* or end() if no elements are greater than @a val.
* @ingroup binary_search_algorithms
*/
template<typename _ForwardIterator, typename _Tp>
_ForwardIterator
upper_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
__glibcxx_requires_partitioned_upper(__first, __last, __val);
_DistanceType __len = std::distance(__first, __last);
while (__len > 0)
{
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
if (__val < *__middle)
__len = __half;
else
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
}
return __first;
}
分享到:
相关推荐
二分查找及其变种,c++ upper_bound,c++ lower_bound(csdn)————程序
RANDINTEGERS(LOWER_BOUND,UPPER_BOUND) 是一个单行函数,它使用 RAND 返回两个指定整数 LOWER_BOUND 和 UPPER_BOUND(具有统一概率)(和替换)之间并包含它们的随机整数。 第三个参数 M_SIZE 是可选的。 如果指定...
Estimating the φ(n) of Upper_Lower Bound in its RSA Cryptosystem
代码包含set使用中的size,insert,count,find,erase,swap,lower_bound,upper_bound,equal_range方法以及详细例子,并设立类和对象,可以看出set如何对对象进行排序和其他操作。
13. lower_bound / upper_bound //要求区间有序 34 14. binary_search //要求有序区间 35 15. merge / inplace_merge 35 16. includes 36 17. set_union, set_intersection, set_difference, set_symmetric_diffrece...
遗传算法+NSGAII+带精英策略的非支配排序的遗传算法+锦标赛选择法+python源码实例(python3.5) 运行之前,evolution_lib.py中注释...#from evolution_search_nsga import parameter_lower_bound,parameter_upper_bound
set中数据是有序的,可以直接搭配lower_bound或者upper_bound使用 相似的数集简单版-SET setaaa[52],a[i]中的每一个元素都是setaaa; num2是两个数集中相同的元素个数; NOIP 题海战-SET-1 说说易错的地方: 可能...
目录传送门题意:思路:代码: 传送门 题意: 思路: ...#define lb lower_bound #define ub upper_bound #define fi first #define se second #define all(x) (x).begin(),(x).end() #define SZ(x) (
传送门 题意: 找规律,题意就是有多少种方式填充该图形 ...#define lb lower_bound #define ub upper_bound #define fi first #define se second #define all(x) (x).begin(),(x).end() #define SZ(x) ((int)(x)
目录传送门题意:思路:代码: 传送门 题意: 思路: 构造的欧拉回路是 1 2 1 3 1 4 1 5……1 n 2 3 2 4 2 5……2 n 3 4 3 5……3 n ...#define lb lower_bound #define ub upper_bound #define fi
目录传送门题意:思路:代码: 传送门 题意: 思路: 就是让判断给出的数据是否合理 两个p,c p,c肯定是是增加的,要么不变 ...#define lb lower_bound #define ub upper_bound #define fi first #defi
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的...#define lb lower_bound #define ub upper_bound #define rep(i,a,b) for(int i=a;i=b;i--) typedef long long l
传送门 题意: 给两个整数u,v,构造一个数组,使得数组的异或和等于u,数组的和等于v 要求构造的数组尽可能的短 ...#define lb lower_bound #define ub upper_bound #define rep(i,a,b) for(int i=a;i=b;i--) type
传送门 题意: 给一个n,输出一个长度为n的数,这个数不能整数每一位 思路: 2333333333即可 ...#define lb lower_bound #define ub upper_bound #define debug(x) cout<<x<<endl #define re
传送门 题意: 给一个数组,然后让你找一个满足题意的排序方式 思路: 先从小到大排序, 拿第一个举例 -2,4,5,5,6,8 ...#define lb lower_bound #define ub upper_bound #define fi first #d
lower_bound (cppmultimap) lower_bound (cppmultiset) lower_bound (cppset) malloc (stdmem) max_size (cppdeque) max_size (cpplist) max_size (cppmap) max_size (cppmultimap) max_size (cppmultiset) ...
lower_bound 或 upper_bound 实现 用 python 试过,但用 TO 失败了。 使用bisect库bisect 。 关键是使用数组 有2个禁止组合,3个可选组合 此处,为禁用组合创建数组而不是可选组合,并将可选组合替换为禁用组合是...
灵活运用库函数lower_bound和upper_bound 单调栈 ★ 通常跟数组有关 迪杰斯特拉算法/弗洛伊德 ★ 通常不考 字典树 ★ 出现前缀字符串查询或者异或值直接用 高精度 ★ 大数乘法或大数加法 注意 数值较大的结果考虑用...
条款45: 注意count、find、binary_search、lower_bound、upper_bound和equal_range的区别 条款46: 考虑用函数对象代替函数作为算法的参数 条款47: 避免产生只写代码 条款48: 总是#include适当的头文件 条款49: ...
条款45: 注意count、find、binary_search、lower_bound、upper_bound和equal_range的区别 条款46: 考虑用函数对象代替函数作为算法的参数 条款47: 避免产生只写代码 条款48: 总是#include适当的头文件 条款49: ...