二分搜索法:通过不断缩小解的可能存在的范围,从而得到求得最优解的方法.
二分搜索法查找符合值的操作思路:
1.先将一批数排好序(后面的分析与题目应用默认升序)
2.进行二分查找,先找到符合条件的值(没有找到符合条件的值,就根据找出的值与条件的关系,通过二分来
缩小范围,直到先找到符合条件的值)
3.如果题中要求找符合条件尽量小的,在已找到符合条件的值的情况下,就可以不断减小上界,进行二分查找
使其值不断减小,直到找到不符合条件的情况为止,则找到的最后一个符合条件的值即为最小(反之亦然)
二分搜索法查找值的例题:
lower_bound:给定长度为n的单调不下降序列a[n]和一个数k,求满足a[i]>=k条件的最小的i.无解则输出n
分析:简单的二分查找,先找到满足a[i]>=k的i,然后在不断向右二分搜索使i的值在满足条件的情况下尽可
能大即可.
代码:
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=1e6+5;
int n,k,rst;
int a[MAX_N];
void binary(int low,int high) {
rst=-1;
int mid;
while (low<=high) {
mid=(low+high)/2;
if (a[mid]>=k) {
rst=mid;
high=mid-1;
}
else low=mid+1;
}
}
int main() {
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
binary(1,n);
printf("%d",rst-1);
}
二分查找值的灵活应用:
对于一些问题,如果我们可以较为容易的判断一个值是不是满足题目的要求,且在不满足情况下,明确知道
该值与正解相比是偏大还是偏小,我们便可以利用到二分查找可以快速定位到所需要的值的特点,来对值进
行二分查找,寻找符合条件的解
处理这类问题的一般思路:
1.先分析题目,判断其能不能用该方法.需满足两个条件:
(1).较为容易的判断一个值是不是满足题目的要求 (2).在不满足的情况下,知道这个值是偏大还是偏小
2.写出判断值满不满足题目要求的函数,该函数以所试的值为参数,返回true或false.(一般函数名为:isok)
3.进行二分查找,一般来说最小值取0,最大值可以取INF(因为二分查找定位速度很快,不担心TLE),然后便
与二分搜索法查找值类似,找出题目要求的值即可.
4.补充说明:此处结束的条件一般有两种情况:(1).如果题目有精度要求,如在小数点保留两位情况下,一般
二分搜索操作100次即可满足条件 (2).如果所输出的值为整数,则一般上下界的差值<=1即可结束
二分查找值的灵活应用的例题:
1.Aggreessive cows:有N间牛舍的小屋,牛舍排在一条线上,第i号牛舍在x[i]的位置,每间牛舍只能放一头
牛,现在共有M(M<=N)头牛,问如何安排,使得最近两头牛的距离能够最大
分析:本题便可用二分查找值,对这个最大距离进行二分查找,找到符合可以放入M头牛的最大距离即可.
所以先写判断条件的函数isok,在进行二分查找最大值即可
代码:
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+5;
const int INF=0x7fffffff;
int N,M,ans;
int x[MAX_N];
bool isok(int d) {
int cur,last=1;
for (int i=2;i<=M;i++) {
cur=last+1;
while (x[cur]-x[last]<d&&cur<=N) cur++;
if (cur>N) return false;
else last=cur;
}
return true;
}
int main() {
scanf("%d%d",&N,&M);
for (int i=1;i<=N;i++) scanf("%d",&x[i]);
sort(x,x+N+1);
int l=0,r=INF,mid;
while (r-l>1) {
mid=(l+r)/2;
if (isok(mid)) {
ans=mid;
l=mid;
}
else r=mid;
}
printf("%d",ans);
}
2.最大化平均值:有n个物品重量和价值分别为w[i]和v[i].从中求出k个物品使得单位重量的价值最大
分析:本题对最大价值进行查找,看这个最大价值是否符合条件即可
代码:
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=1e4+5;
const double INF=1000005.;
int n,k;
int w[MAX_N],v[MAX_N];
double ans;
bool isok(double x) {
double y[MAX_N];
double sum=0;
for (int i=1;i<=n;i++) {
y[i]=v[i]-w[i]*x;/*如果想使单位重量的价值为x,则w[i]重量的价值为w[i]*x,所以我们计算
y[i]即为选了这个物品和我们预期要得到的价值的差值*/
}
sort(y+1,y+n+1,greater<int>());//要优先选择能获得更高价值的物品,对y[i]进行一个升序排序
for (int i=1;i<=k;i++) {
sum+=y[i];
}
return sum>=0;/*如果按照这种最好的选法得到的价值和预期的价值的差值>=0就表示可达到预期
价值,即该方案可行*/
}
int main() {
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]);
double l=0.,r=INF,mid;
for (int i=0;i<100;i++) {
mid=(l+r)/2;
if (isok(mid)) {
ans=mid;
l=mid;
}
else r=mid;
}
printf("%.2f",ans);
}