学术计划VOL.1 二分！
2025-10-11 21:37:40
发布于：重庆
234阅读
0回复
0点赞
二分！
这是Stars_Seeker推出的一个新系列的第一期，希望这个系列能够帮助到刚学习 C++ 或者复习 C++ 却不知道复习哪些的同学们，同时这个系列没有过多的言语和绝美的佳句作者语文不好（，只有透彻的知识awa。
写的这么差的帖子肯定不是AI（
二分的前提：单调性（单调增 单调减 单调不增 单调不减）
二分的思想：每次从中间将区间分成两半 ，每次选择往左走或者向右走 。
二分的复杂度：每次区间长度减半，可以看成是 n 每次除以 2，直到n = 1时候结束 ， 这一过程是 O(logn) 。
二分的2种写法：
求符合条件的最左边
while(l<r){
int mid=l+r>>1;
if(check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
求符合条件的最右边
while(l<r){
int mid=l+r+1>>1;
if(check(mid)){
l=mid;
}
else{
r=mid-1;
}
}
二分查找两个函数
lower_bound(a+1,a+1+n,x) 查找大于等于x的第一个位置
upper_bound(a+1,a+1+n,x) 查找严格大于x的第一个位置
返回的都是地址
假如你想要得到下标，可以这么写：
int p=lower_bound(a+1,a+1+n,x)-a; //减去首地址 获得偏移量
找不到的话 返回 a+n+1的地址（我们的范围在下标 1~n, 所以返回n + 1的地址代表找不到）
是的没错，你没有听错，第一期结束了！
二分除了固定的模版其余的重点就是check函数的部分了，因为每道题check都可能不太一样，所以就不花时间去讲了awa，还是那句话：菜就多练，做多了自然就熟了！
《4591》
有帮助，赞一个