二分查找

二分查找

1、整数二分

bool check(int x) { /*...*/ } //检查x是否满足某种性质

//适用于区间[l,r]被划分成[l,mid],[mid+1,r]时使用，也就是ture分在左半边
int bsearch_1(int l, int r)
{
	while (l < r)
	{
		int mid = l + r >> 1;
		if (check(mid))r = mid;
		else l = mid + 1;
	}
	return l;
}

//适用于区间[l,r]被划分成[l,mid-1],[mid,r]时使用，也就是ture分在右半边
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;
}

2、浮点数二分

bool check(double x) { /*...*/ } //检查x是否满足某种性质

//浮点数二分
double bsearch_3(double l, double r)
{
	const double eps = 1e-6;  //eps,表示精度取决于题目对精度的要求，小数点4位为1e-6,6位为1e-8，以此类推
	while (r - l > eps)
	{
		double mid = (l + r) / 2;
		if (check(mid))r = mid;
		else l = mid;
	}
	return l;
}