【算法】二分法和三分法

知识点

一 . 二分法

洛谷P2249 【深基13.例1】查找（另有方法未完成）

题目描述

输入 个不超过 的单调不减的（就是后面的数字不小于前面的数字）非负整数 ，然后进行 次询问。对于每次询问，给出一个整数 ，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。

输入格式

第一行 2 个整数 n 和 m，表示数字个数和询问次数。

第二行 n 个整数，表示这些待查询的数字。

第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。

输出格式

m 个整数表示答案。

输入输出样例

输入

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

输出 

1 2 -1 

说明/提示

10^6 规模的数据读入，请用 scanf。用 cin 会超时。

 已AC代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e7+5;
int a[maxn],b[maxn];
int n,m;
int check(int x)
{int l,r;l=1; r=n;    //左端点为1，右端点为n（在n个数据内查找）while(l<r){int mid=l+(r-l)/2;if(a[mid]>=x)	{r=mid;	}else {l=mid+1;}}	if(a[l]==x)	return l;else return -1;		
}int main()
{scanf("%d %d",&n,&m);for(int i=1;i<=n;++i){scanf("%d",&a[i]);}for(int j=1;j<=m;++j){scanf("%d",&b[j]);int result=check(b[j]);cout<<result<<" ";}return 0;
}

思路：

首先找到这串数字中间位置的那个数，然后与需要查询的数比较

如果要查询的数小于中间那个数，那么答案肯定在左边

如果要查询的数大于中间那个数，那么答案肯定在右边

如果等于的话继续在左边找，因为找到的位置还不能确定是第一个数

如此重复，直到要查询的区域变为1。

法2：使用STL(lower_bound(start, end, target)

有些时候，二分不仅仅可以用于查找，还可以解决求“最大的最小值”或“最小的最大值”等双最问题。

应用：二分+最短路

1 . 洛谷 P1948 [USACO08JAN]Telephone Lines S

 思路：

由题得：大于 k 的电话线需要收费，且总费用决定于其中最长的电话线的长度，求将电话线引导震中市最少需要在电话线上花多少钱。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n,p,k;
const int maxn=1e6+5,INF=0x3f3f3f3f;
struct node{int to,next,w;
}edge[maxn<<1];
int head[maxn],num=0;int dis[maxn];
queue <int> q;
bool vis[maxn];inline int read()
{int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}inline void add(int u,int v,int w)
{edge[++num].to=v;edge[num].w=w;edge[num].next=head[u];head[u]=num;
}inline bool spfa(int x)
{memset(dis,INF,sizeof(dis));memset(vis,0,sizeof(vis));q.push(1);dis[1]=0;vis[1]=1;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to,w;if(edge[i].w<=x) w=0; //将所有小于x的边赋值为0，那么不会改变总价，即属于免费的路线else w=1;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(!vis[v]){q.push(v);vis[v]=1;}}}}if(dis[n]<=k) return 1;else return 0;
}int main()
{n=read(); p=read(); k=read();memset(head,-1,sizeof(head));for(int i=1;i<=p;++i){int a=read(),b=read(),l=read();add(a,b,l);add(b,a,l);}int res=-1,r=1000000,le=0; //求二分，这里直接从最大距离开始查找，如果res找不到就输出-1while(le<=r){int mid=(le+r)>>1;if(spfa(mid)) {res=mid; //保存当前答案r=mid-1;}else le=mid+1;}printf("%d",res);	return 0;
}

二 . 三分法

三分法常用于单谷函数求最大值或最小值。

在一个区间 [ l , r ] 中，首先找到  和 （两个三等分点），把查找函数   和  进行比较。

当求的是最小值时： ，则 ；否则 ；

当求的是最大值时：，则 ；否则 ；

离答案越近的就保留，离答案相对远的则作为下一次三分的端点。

模板题

洛谷 P3382 【模板】三分法

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
double l,r;
const double derta=0.000001,maxn=1e5+5;
double a[10010];inline double find(double x)
{double ans=a[0];for(int i=1;i<=n;++i){ans=ans*x+a[i];}return ans;
}inline void check(double l,double r)
{while(r-l>derta){double mid1=(l+r)/2.0;double mid2=(mid1+r)/2.0;if(find(mid1) > find(mid2)) check(l,mid2);else check(mid1,r);}if(r-l<=derta){printf("%.5lf",r);exit(0); //退出函数}
}int main()
{scanf("%d",&n);scanf("%lf%lf",&l,&r);for(int i=0;i<=n;++i){scanf("%lf",&a[i]);}check(l,r);return 0;
}

2 . 洛谷 P1883 函数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
const double derta=1e-9; //两个点之间的差尽可能得小，得到的点的位置就越精确
int a[maxn],b[maxn],c[maxn];
int n;
inline double to_compared(double x) //比较所有函数的最低点，即在区间上的最小值
{double ans=0;for(int i=1;i<=n;++i){ans=max(ans,(x*x*a[i]*1.0+x*b[i]*1.0+c[i]*1.0));}return ans;
}	int main()
{int t;scanf("%d",&t);for(int j=1;j<=t;++j){scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d %d %d",&a[i],&b[i],&c[i]);}	double l=0,r=1000;while(r-l>derta){double mid1=(l+r)/2.0;double mid2=(mid1+r)/2.0;if(to_compared(mid1) < to_compared(mid2)) r=mid2;else l=mid1;}	printf("%.4lf\n",to_compared(l));}return 0;
}