知识点整理（4）二分查找与二分答案
二分，一个看似简单却在细节部分折磨死人的东西。
基础知识点
- 应用前提：要求表中元素以及所求答案按关键字单调有序排列。
- 两者面向的大概问题：在一个有序序列中查找一个想要的数。
二分查找
二分查找的细节大概有三点：
- while循环的结束条件到底是left小于right,还是小于等于。
(l=mid+1 or l=mid) and (r=mid-1 or r=mid)- 计算 mid 时需要技巧防止溢出，建议写成:
mid = left + (right - left) / 2 - 边界为浮点时，循环条件要控制精度，更新区间不能+1（为什么有四点）
对于第一点，我的思路就是，自己把程序在脑中模拟一下，看看最后需不需要将left==right的情况加上（听君一席话了属于是）。
对于第二点的话，主要看mid用不用的上，用得上就要留着，别加1溜了，不过也可以同步用一个变量随时记录当前mid，这样再说。
下面给出一些二分查找的应用场景：
找一个数
最简单的应用，直接上代码，抉择看注释：
class Solution {
public:
int search(vector<int>& nums, int target) {
int l=0,r=nums.size()-1,mid;
while(l<=r){//这边当等于的时候，此时对应的数还没查找，所以要加上
mid=(l+r)/2;//错误示范了属于是
if(nums[mid]==target)return mid;//找到
else if(nums[mid]>target)r=mid-1;//由于这里mid不是所要找的数就没用了，所以不用包括mid
else l=mid+1;
}
return -1;//没找到
}
};找左边界
例子：找序列中大于某个数的第一个数
//并非完全适用请具体问题具体分析
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.size == 0||nums[nums.size()-1]<=target) return -1;
int l=0,r=nums.size()-1,mid;
while(l<r){//这边当等于的时候，此时对应的数已经被check过了，所以不用加上
mid=l+(r-l)/2;//改错就改了属于是
if(nums[mid]>target)r=mid;//由于这里mid可能是所要找的数，所以需要包括mid
else l=mid+1;
}
return r;
}
};
//lower_bound和upper_bound真不错真不搓找右边界
例子：找序列中小于某个数的最后一个数
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.size == 0||nums[nums.size()-1]>=target) return -1;
int l=0,r=nums.size()-1,mid;
while(l<r){//这边当等于的时候，此时对应的数已经被check过了，所以不用加上
mid=l+(r-l)/2;//改错就改了属于是
if(nums[mid]<target)l=mid;//由于这里mid可能是所要找的数，所以需要包括mid
else r=mid-1;
}
return r;
}
};二分答案
- 基本思想：在答案可能的范围内$[L,R]$二分查找答案，检查当前答案是否满足题目的条件要求，根据判断结果更新查找区间。
下面同样给出应用场景：
求最大的最小值
原题链接：洛谷P2678 跳石头
此题是求最大的最短跳跃距离
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 50010;
ll L, N, M;
ll dis[maxn]{0};
bool binary(int x){
ll pre = 0,num=0;
for (int i = 1; i <= N;i++){
if(dis[i]-pre<x){//记录小于最短的，代表要拿开的岩石
num++;
}
else{
pre = dis[i];
}
}
if(num<=M)
return true;
return false;//要拿开的超过了最多岩石的限制
}
int main(){
cin >> L >> N >> M;
for (ll i = 1; i <= N;i++){
scanf("%lld", &dis[i]);
}
ll l = 1, r = L,mid,ans=L;
while(l<=r){//对最短距离进行二分
mid = (l + r) / 2;
if(binary(mid)){//检查答案
ans = mid;//记录ans
l = mid + 1;//return true代表还可以继续往右边搜索
}
else
r = mid - 1;
}
cout << ans;
return 0;
}再来一题：洛谷P1824进击的奶牛
#include<cstdio>
#include<algorithm>
using namespace std;
const int lnf = 1e9;
const int max_N = 100010;
int N[max_N]{0};
int n,m,ans{0};
bool judge(int mid){
int last{-lnf},count{0};
for (int i = 1; i <= n;i++){
if(N[i]-last>=mid){
last = N[i];
count++;
}
}
return count >= m;
}
int main(){
scanf("%d %d", &n, &m);
for (int i = 1; i <= n;i++){
scanf("%d", &N[i]);
}
sort(N + 1, N + n);
int L{0}, R{lnf},mid;
while(L<=R){
mid = L + R >> 1;
if(judge(mid)){
L = mid + 1;
ans = max(ans, mid);
}
else{
R = mid - 1;
}
}
printf("%d", ans);
return 0;
}求最小的最大值
原题链接：洛谷P1525关押罪犯
此题实则是求最小的最大矛盾值，下面的题解的check函数中使用的是bfs来进行二分图染色，染色成功就返回true，而且下面的二分中涉及到了另外一种二分方式，即通过target的相邻元素是否在答案区间中来判断。
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+15;
int n,m,sum;
int head[maxn];
struct node{int to;int z;int next;}edge[maxn*2];
inline int read()//快读
{
char ch;
int fu=1,x=0;
for (ch=getchar(); ch<=32; ch=getchar());
if (ch=='-') fu=-1,ch=getchar();
for (x=0; ch>32; ch=getchar()) x=x*10+ch-48;
return x*fu;
}
void add(int x,int y,int z)//存有向图
{
edge[++sum].next=head[x];
edge[sum].to=y;
edge[sum].z=z;
head[x]=sum;
}
bool bfs(int midd) //bfs进行二分图染色
{
int color[maxn];
memset(color,0,sizeof(color));
queue <int> q;
for (int j=1;j<=n;j++)
{
if (color[j]) continue;
q.push(j);color[j]=1;
do
{
int k=q.front();q.pop();
for (int i=head[k];i;i=edge[i].next)
if (edge[i].z>=midd)//矛盾值大于等于所给值就进行二分图染色（题目中表示放在两个监狱）
{
if (color[edge[i].to]==0) {
color[edge[i].to]=color[k]==1?2:1;
q.push(edge[i].to);
}
else if (color[edge[i].to]==color[k]) return false; //表示染色失败
}
}while (!q.empty());
}
return true;
}
int main()
{
int maxx;
n=read();m=read();
for (int i=1;i<=m;i++)
{
int a,b,c;
a=read();b=read();c=read();
maxx=max(maxx,c);
add(a,b,c);
add(b,a,c);
}
int l=0,r=maxx+1,midd;
while (l+1<r)//这里注意！
{
midd=(l+r)>>1;
if (bfs(midd)) r=midd;
else l=midd;
}
printf("%d",l);
return 0;
}求满足条件的最大（小）值
原题链接：hdu 1969平均分pie
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const double eps = 1e-10;
const double pi = 4*atan(1.0);
int n,f,arr[10100];
bool check(double r)
{
double s = r*r;
int num = 0;
for(int i=1; i<=n; ++i)
{
double tep = arr[i]*arr[i];
num += (int)(tep/s);
}
return num >= f+1? true : false;//f+1因为要分给自己
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>f;
for(int i=1; i<=n; ++i)
cin>>arr[i];
double l = 0.0;
double r = 10100.0;
while(fabs(r-l)>eps) //注意精度,相当于浮点数版本的l<r
{
double mid = (l+r)/2.0;
if(check(mid))
l = mid;
else r = mid;
}
printf("%.4f\n",r*r*pi);
}
return 0;
}