二分写法讲解

Veröffentlicht am | in

二分法

如果序列可以被分成两个不同性质的部分，而我们想找到分界线的时候，我们就能使用二分法。
很简单的例子就是当我们去猜一个数字的时候，如果返回的是大了还是小了，我们总会使用二分的办法去寻找。
另外一种二分是浮点数的二分，两种二分写法上有很大的不同，所以分开讲。

序列二分

怎样写个不会错的二分往往是个困难的事情，但是现在我说一下自己的一些心得和技巧。

使用半开半闭区间

为什么要使用半开半闭区间呢？这是为了保证我的答案一定能从一个确定的指针中得到，而不是最后的时候把$L$,$R$都检查检查。
我们保证我们最后要的答案的位置check函数是返回true的，故而拥有和我们要的位置有着同样性质的部分都是返回true的。
这样一来，只要我们一开始保证$L,R$中有一个是返回true的，一个是返回false的，那么二分就可以向下面那样写。
比如我们保证$R$所指示的位置的性质是返回true的（换句话说序列的分界线右边都是返回true的，而我们需要的是第一个返回true的位置）

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(int m){
	//如果是我们要的部分，返回true，否则false
}
int binarySearch(){
	int L=-1,R=n;//一开始保证L一定是返回false的，R一定是返回true的
	while(R-L>1){//循环直到打破半开半闭区间的大小限制
		int m=(R+L)>>1;//取中间
		if(check(m))R=m;//如果返回true，说明中间落在闭区间范围
		else L=m;//否则落在开区间范围
	}
	return R
}

浮点数的二分

这种二分一般在计算集合中比较常见，这种二分的好处在于是好写。

控制二分的次数

为了避免相对误差带来的各种麻烦，我们应该控制二分的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(double m){
	
}
double binarySearch(){
	double L=-INF,R=INF;
	for(int t=0;t<100;t++){
		double m=(L+R)/2;
		if(check(m))L=m;
		else R=m;
	}
	return L;
}