欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分答案模板

程序员文章站 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;
	}
}
相关标签: 算法