算法基础学习笔记——②二分
✨博主：命运之光 ✨专栏：算法基础学习
前言：算法学习笔记记录日常分享，需要的看哈O(∩_∩)O，感谢大家的支持！
✨二分
🍓整数二分
1.有单调性一定可以二分，没有单调性也可能二分 2.二分的本质是边界，只要找到某种性质，使得整个区间一分为二， 那么就可以用二分把整个边界点二分出来
二分红色分界点时
解释这里为什么要+1：如果当l=r-1时, 不加1时mid=(l+r)/2=l(要下取整，1被略掉）,进行if(check(mid))如果为 true,则更新l=mid,可此时mid算出还是=l,故进入死循环） 此处check是否满足红色性质
区间[l, r]被划分成[l, mid -1]和[mid, r]时使用：
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;
}
此处check是否满足绿色性质
区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r){
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}简单理解：mid的值不在所求答案区间（故找答案区间旁边的区间求mid的值）
🍓整数二分模板：
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid -1]和[mid, r]时使用：
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;
}//关于while的理解： while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } eg. 1 2 4 5 6 中查找3（答案没有） 每个数字的标号：0 1 2 3 4 第一次进入while循环： mid=(0+4)/2=2,q[mid]=4; If(q[mid]>=3)r=mid=2; 第二次进while循环： mid=(0+2)/2=1,q[mid]=2; if(q[mid]>=3)r=mid; 显然q[mid]❤️, else l=mid+1=2; 现在l=r=2进入不了循环且q[l]!=3,（这里q[l]=q[r]就是最终二分彻底的值故没有找到3
🍓浮点数二分
当l～r足够小（≤[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-H8YrNrO8-1685067877207)(null#card=math&code=10^{-6}&id=a4G1L)]）就可以用l或r当作答案
🍓浮点数二分模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r -l > eps)//写法2：for(int i=0;i<100;i++) //不用精度，直接循环100次也可以
{
double mid = (l + r) / 2;//注意：这里不能写>>1,int时可进行>>1操作
if (check(mid)) r = mid;
else l = mid;
}
return l;
}小贴士：
🍓整数二分步骤：
1.找一个区间[L,R],使得答案一定在该区间中； 2.找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点； 3.分析终点M在该判断条件下是否成立，如果成立，考虑答案在哪个区间：如果不成立，考虑答案在哪个区间； 4.如果更新方式写的是R=Mid,则不用做任何处理；如果更新方式写的是L=Mid,则需要在计算Mid时加上1。
遇见二分先画图
🍓二分模板2：
int 1=1,r=n,res;
while(1<=r)
{
int mid=(1+r)/2;
if(check(mid))
{
r=mid-1;
res=mid;
}
else l=mid+1;
}
while(1<=r)
{
int mid=(1+r)/2;
if(check(mid))
{
1=mid+1;
res=mid;
}
else r=mid-1;
}腾讯云开发者
