二分
作者:
TyjCj
,
2022-08-24 17:54:40
,
所有人可见
,
阅读 177
\\lower_bound寻找>=x的第一个数,应该说lower_bound对应二分第一个模板
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
\\二分第二个模板找的是最后一个大于等于x的数
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
lower_bound(a,a+n,x) - a 返回第一个大于等于x 当前目标值指针
upper_bound(a,a+n,x) - a 返回第一个大于x 当前目标值指针
lower_bound(a,a+n,x,greater<int>()) - a 返回第一个小于等于x 当前目标值指针
upper_bound(a,a+n,x,greater<int>()) - a 返回第一个小于x 当前目标值指针