二分答案模板
程序员文章站
2024-03-17 15:34:16
...
我注意到二分答案算法对于mid的判定不一定总是只有真假二态的。
例如:高精度除法使用二分,当刚好整除时,可直接结束二分。
虽然传统二态也可以得到正确答案,但耗时多一点。
状态数与实际越相同,二分次数越少(但目前只遇到了三态)。
离散二态:
while(l<=r){
mid=(l+r)/2;
if(judge(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
离散三态:
int type;
while(l<=r){
mid=(l+r)/2;
type=judge(mid);
if(type==1){
ans=mid;
r=mid-1;
}
if(type==0) l=mid+1;
if(type==-1){
ans=mid;
break;
}
}
连续三态:
int type;
while(r-l<=eps){
mid=(l+r)/2; //注意使用double类型;
type=judge(mid);
if(type==1){
ans=mid;
r=mid;
}
if(type==0) l=mid;
if(type==-1){
ans=mid;
break;
}
}
上一篇: python中部分函数用法的总结