Skip to main content

二分

参考资料​

二分法​

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

函数 check 的返回值应为 { 0,0,…,0,0,1,1,…,1,1 }\set{0,0,\dots,0,0,1,1,\dots,1,1}。

二分后 ll 为第一个 11 的位置；l−1l-1 为最后一个 00 的位置。

三分法​

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

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

例题​

洛谷 P2249 【深基13.例1】查找​

洛谷 P2249 【深基13.例1】查找

输入 nn 个不超过 10910^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,ana_1,a_2,\dots,a_{n}，然后进行 mm 次询问。对于每次询问，给出一个整数 qq，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1-1。

Code (1)
#include <bits/stdc++.h>
using namespace std;

const int N=1000005;
int a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	while(m--)
	{
		int q;
		cin>>q;
		int k=lower_bound(a+1,a+n+1,q)-a;
		cout<<(a[k]==q?k:-1)<<' ';
	}
	return 0;
}

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

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

给定 nn 个形如 ax2+bx+cax^2+bx+c 的二次函数 f1(x),f2(x),…,fn(x)f_1(x),f_2(x),\dots,f_n(x)，设 F(x)=max⁡fi(x)F(x)=\max f_i(x)，求 F(x)F(x) 在区间 [0,1000][0,1000] 上的最小值。

Code (1)
#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 m1=(l*2+r)/3,m2=(r*2+l)/3;
			if(f(m1)<f(m2))r=m2;
			else l=m1;
		}
		cout<<fixed<<setprecision(4)<<f(l)<<'\n';
	}
	return 0;
}

洛谷 P3382 三分​

洛谷 P3382 三分

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

Code (1)
#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 m1=(l*2+r)/3,m2=(r*2+l)/3;
		if(f(m1)>f(m2))r=m2;
		else l=m1;
	}
	cout<<fixed<<setprecision(6)<<l<<'\n';
	return 0;
}