二分
在递增序列中查找>=x的最小值
在递增序列中查找<=x的最大值
特点
两个主要的区分在于取mid的方法不同,并且在mid=(l+r)/2
时mid不会背取到r;在mid=(l+r+1)/2
时mid不会被取到l
。这是对于区间[1,n]
可以分别扩充到[1,n+1]
以及[0,n]
,如果最后的返回值落在了扩充的区间边界上就证明在该区间内无解。
两个二分查找的函数
lower_bound
返回首个不小于Mdp的迭代器 int low= lower_bound(dp+1,dp+n+1,Mdp)-dp;
lower_bound
返回首个大于Mdp的迭代器 int low= upper_bound(dp+1,dp+n+1,Mdp)-dp;