0x04 二分

两种二分写法：

int l = 0, r = n + 1;
	while(l < r)
	{
		mid = l + (r - l) / 2;
		if(a[mid] >= x) r = mid;
		else l = mid + 1; 
		
	}

	while(l < r)
	{
		mid = (l + r + 1) << 1;
		if(a[mid] <= x) l = mid;
		else r = mid - 1;
	}

1、循环条件 l < r

可以保证最终l == r此时mid一定落在正确答案上

2、l 与 r 的改变

第一种是找出lower_bound(x)，大于等于x的最小的数字,当a[mid] >= x,mid之后的数字肯定都不满足，而mid可能是正确答案，因此r = mid；当a[mid] < x, mid一定不是正确答案，所以l = mid + 1;

第二种是找出小于等于x的最大数字,当a[mid] <= x, mid之前的数字肯定都不满足，而mid可能是正确答案，因此l = mid；当a[mid] > x, mid一定不是正确答案，所以r = mid - 1;

3、mid的改变 + [0, n+1]

mid = l + (r - l) / 2 可以防止溢出

而mid = (r + l + 1) << 1 使得mid不会等于l，避免当r - l = 1时，mid始终等于l，当进入l = mid语句后形成死循环的情况；

而将原本的区间[1, n]扩大到[0, n+1]可以处理无解的情况

总结:具体情况具体分析

1、根据a[mid] 与 目标值的比较结果，选取相应的左右半区间

2、根据要寻找的目标值，判断mid + 1, mid - 1能否确定不是正确答案，随后选用配套的两种二分方案之一:"r = mid, l = mid + 1, mid = l + (r - l) / 2" and "l = mid, r = mid - 1, mid = (l + r + 1) << 1" 中的一种

3、终止条件为l == r，此时该位置为最终答案。

实数域上的二分

1、一般要保留k位小数的时候，取精度eps = 1e-(k+2)

2、while条件为l + eps < r

while(l + eps < r)
	{
		double mid = (l + r) / 2;
		if(calc(mid)) l = mid;
		else r = mid;

3、若难以确定精度，则利用固定循环次数进行二分，往往甚至精度更高

For(i, 1, 100)
	{
		double mid = (l + r) / 2;
		if(calc(mid)) l = mid;
		else r = mid;
	}

例 aw102前置例题 最大矩阵和--POJ1050

int main ()
{	
	cin >> n;
	For(i, 1, n)
		For(j, 1, n) cin >> mat[i][j];
	For(i, 1, n)
	{
		clr(s);
		For(j, i, n)
		{
			For(k, 1, n) s[k] += mat[j][k];
			int num = 0;
			For(k, 1, n)
			{
				num += s[k];
				if(num <= 0) num = 0;
				ans = max(ans, num);
			}
		}
	}
	cout << ans << endl;
	return 0;
}	

遍历第i行到第j行，同时在不同i的情况下用sum保存第i行到第j行每一列的和，每保存完第j行，求一次最大子数组和，并与ans比较，以此做到了将二维变成了一维，并将所有不同行的矩阵求得了最大子矩阵之和，最终得到最大矩阵之和

例 aw102 最佳牛围栏

题目链接:102. 最佳牛围栏 - AcWing题库

题目大意：求所有长度不小于L的子序列中最大的平均数(子序列之和/子序列长度)

思路分析：实数域二分+前缀和

我们可以将求最大平均数 通过将序列每一项减去平均数 转化为求长度≥L的子序列之和为非负，既然要最大平均数，因此所得到的非负子序列之和越大则越优(因为这段子序列每一项可以减去更大的平均数，依然保证非负)，即求能使得序列每一项减去自己后，最大子序列和非负的最大平均数

**解题步骤：1、先用实数域二分求得平均数 **

	double l = 0, r = 1e6;
	double mid;
	double eps = 1e-5; //保留三位小数
	while(l + eps < r) //实数域二分
	{
		mid = (l + r) / 2;
		if(check(mid)) l = mid;
		else r = mid;  
	} 

​ 2、利用该平均数生成一个新的序列，并求前缀和

​ 3、利用前缀和思想求新序列的最大子序列之和，并判断是否≥0

bool check(double mid)
{
	For(i, 1, n) s[i] = s[i-1] + a[i] - mid; //步骤2 求新序列的前缀和
	double minn = 1e6;
	for(int i = 0, j = f; j <= n; j++, i++) //利用二指针的思想，先将指针的位置差设为L，随后每次循环同步加1
	{
		minn = min(minn, s[i]); //minn一定为当前所有S[j]能减的最小前缀和，且减去最小的即为最大的子序列之和
		if(s[j] - minn >= 0) return true; //符合条件继续二分求最优解
	}
	return false;
}

完整Code：

//#pragma comment(linker,   "/STACK:10240000000000,10240000000000")
//#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define For(i,a,b) for (int i=(a);i<=(b);++i)
#define Fod(i,b,a) for (int i=(b);i>=(a);--i)
#define mls multiset
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pob pop_back
#define itt iterator
#define clr(x) memset(x, 0, sizeof(x));

typedef long long ll;
typedef unsigned long long ull;
		
using namespace std;
const int MAXN = 0x7fffffff;

int n, f;
double a[100005];
double b[100005];
double s[100005];

bool check(double mid)
{
	For(i, 1, n) s[i] = s[i-1] + a[i] - mid;
	double minn = 1e6;
	for(int i = 0, j = f; j <= n; j++, i++)
	{
		minn = min(minn, s[i]);
		if(s[j] - minn >= 0) return true;
	}
	return false;
}

int main ()
{	
	cin >> n >> f;
	For(i, 1, n) cin >> a[i];
	double l = 0, r = 1e6;
	double mid;
	double eps = 1e-5;
	while(l + eps < r)
	{
		mid = (l + r) / 2;
		if(check(mid)) l = mid;
		else r = mid;  
	} 
	cout << (int)(r*1000) << endl; 
	return 0;
}