二分答案题目的一些经验规律

思路基础

将一个序列分成左侧的蓝色区域和右侧的红色区域，

那么我们有基础代码如下

代码CPP · 18 行

int search(int left,int right){
	int mid;
	while(left+1!=right){
		mid=left+(right-left>>1);
		if(isBlue(mid)) left=mid; // if(isRed(mid)) right=mid;
		else right=mid; //left=mid;
	}
	return left; //return right;
	/*
	if(check(right)) return right;
	else return left;
	*/

	/*
	if(check(;eft)) return left;
	else return right;
	*/
}

下面我们来逐一解析这里面的区别。

求最小值的最大的问题

这种情况下我们需要写isBlue()函数，循环体内如下

while(left+1!=right){
    mid=left+(right-left>>1);
    if(isBlue(mid)) left=mid; 
    else right=mid; 
}

注意isBlue()最后的返回的不等式要取等，将答案纳入蓝色边界内。

然后最后返回left。

但是如果没有AC，那么可能是因为边际条件的问题。

我们需要这样写返回值：

if(isBlue(right)) return right;
else return left;

这样可以保证输出是最大的可能答案。

求最大值的最小的问题。

这种情况下我们需要写isRed()函数，循环体内如下

while(left+1!=right){
    mid=left+(right-left>>1);
    if(isRedmid)) right=mid; 
    else left=mid; 
}

注意isRed()最后的返回的不等式要取等，将答案纳入红色边界内。

然后最后返回right。

但是如果没有AC，那么可能是因为边际条件的问题。

我们需要这样写返回值：

if(isRed(left)) return left;
else return right;

这样可以保证输出是最小的可能答案。