二分

参考资料

• 二分 - OI Wiki
• 整数范围二分的正确写法 - bilibili

实现

整数

int l=x,r=y+1;
while(l<r)
{
	int mid=l+r>>1;
	if(check(mid))r=mid;
	else l=mid+1;
}

实数

double l=x,r=y;
while(r-l>eps)
{
	double mid=(l+r)/2;
	if(check(mid))r=mid;
	else l=mid;
}

提示

• 函数 check 的返回值应为 $\{0,0,\cdots,0,0,1,1,\cdots,1,1\}$。
• 二分后 $l$ 为第一个 $1$ 的位置；$l-1$ 为最后一个 $0$ 的位置。

拓展

三分

double l=x,r=y;
while(r-l>eps)
{
	double lmid=(l*2+r)/3;
	double rmid=(r*2+l)/3;
	if(f(lmid)>f(rmid))r=rmid;
	else l=lmid;
}

提示

单峰函数如果有最大值 f(lmid)>f(rmid)；如果有最小值 f(lmid)<f(rmid)。

例题

洛谷 P1883 【模板】三分 | 函数

洛谷 P1883 【模板】三分 | 函数

给定 $n$ 个形如 $ax^2+bx+c$ 的二次函数 $f_1(x),f_2(x),\dots,f_n(x)$，设 $F(x)=\max f_i(x)$，求 $F(x)$ 在区间 $[0,1000]$ 上的最小值。

#include <bits/stdc++.h>
using namespace std;

const double eps=1e-9;
const int inf=0x3f3f3f3f;
const int N=10005;
double a[N],b[N],c[N];
int n;
double f(double x)
{
	double res=-inf;
	for(int i=1;i<=n;i++)
	{
		res=max(res,a[i]*x*x+b[i]*x+c[i]);
	}
	return res;
}
int main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i]>>b[i]>>c[i];
		}
		double l=0,r=1000;
		while(r-l>eps)
		{
			double lmid=(l*2+r)/3;
			double rmid=(r*2+l)/3;
			if(f(lmid)<f(rmid))r=rmid;
			else l=lmid;
		}
		cout<<fixed<<setprecision(4)<<f(l)<<'\n';
	}
	return 0;
}

洛谷 P3382 三分

洛谷 P3382 三分

给出一个 $N$ 次函数，保证在范围 $[l, r]$ 内存在一点 $x$，使得 $[l, x]$ 上单调增，$[x, r]$ 上单调减。试求出 $x$ 的值。

#include <bits/stdc++.h>
using namespace std;

const double eps=1e-6;
const int N=15;
double a[N];
int n;
double f(double x)
{
	double res=0;
	for(int i=n;i>=0;i--)res=res*x+a[i];
	return res;
}
int main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	double l,r;
	cin>>n>>l>>r;
	for(int i=n;i>=0;i--)
	{
		cin>>a[i];
	}
	while(r-l>eps)
	{
		double lmid=(l*2+r)/3;
		double rmid=(r*2+l)/3;
		if(f(lmid)>f(rmid))r=rmid;
		else l=lmid;
	}
	cout<<fixed<<setprecision(6)<<l<<'\n';
	return 0;
}