obj/Release/netcoreapp2.2/PubTmp/Out/wwwroot/data/blogs/二分查找.md

微信扫码关注公众号，代码整理好后第一时间通知你。

### 二分查找

#### 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;
}
~~~~