算法进阶——二分

二分法：

一种高效查找方法，将问题搜索范围一分为二，迭代地缩小范围，直到找到目标。

二分法适用于有序的数据集合。

常见的二分类型有：

整数二分

浮点二分

二分答案

二分解题步骤：

1.研究并发现数据结构的单调性

2.确定最大区间[l，r]，确保分界点一定在里面

3.确定check函数，一般为传入的mid(区间中的某个下标)，返回mid所属区域或返回一个值，当check函数较简单时可以直接判断。

4.计算中点mid=(l+r)/2，用check判断该移动l或r指针

5.返回l或r

模板代码：

int l=0,r = 1e9;
while (l+1!=r){
    int mid = (l+r)/2;
    if(a[mid]>=x)
        r= mid;
    else
        l=mid;
    }
    cout<<r<<endl;    

}

整数二分例题（lanqiao OJ 1389）：

题目描述

给定一个数组，其采用如下代码定义：

int data[200];
for(i = 0 ; i < 200 ; i ++）data[i] = 4 * i + 6;

现给定某个数，请你求出它在 data 数组中的位置（下标）。

输入描述

输入一个待查找的整数（该整数一定在数组 data 中）。

输出描述

输出该整数在数组中的指标。

输入输出样例

示例 1

输入

262

输出

64

示例 2

输入

438

输出

108

示例 3

输入

774

输出

192

#include <bits/stdc++.h>
using namespace std;
int main(){
    int data[200];
    int n,left,right,mid;
       for(int i = 0 ; i < 200 ; i++){
           data[i] = 4 * i + 6;
    }
    cin >>n;
    left=0,right=199;
    while(left < right){
        mid=(left+right)/2;
        if(data[mid]>n){
            right=mid-1;
        }else if(data[mid]<n){
            left=mid;
        }else{
            cout<<mid<<endl;
            break;
        }
    }
    return 0;
}

浮点二分：

浮点二分模板：

double l =0, r = 1e9,eps =1e6-6;
while (r-l>=esp){//这里的esp为一个极小值
    doiuble mid = (l+r)/2;
    if(f(mid)>=0)
        r= mid;
    else
        l =mid;
 
}
 cout<<r<<endl;

二分答案：

二分答案模板：

bool check (int mid){
    bool res = ture;
    return res;
}

int main(){

    int l=0,r=1e9;
    while (l+1!=r){
        int mid = (l+r)/2;
        if(check(mid))
            l =mid;
        else
            r=mid;
    }
    cout<<l<<endl;
    return 0;
}

check函数根据题意写

二分答案例题（lanqiao OJ 364）可以去试一下（洛谷 OJ3853）

一年一度的"跳石头"比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 NN 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走MM 块岩石（不能移走起点和终点的岩石）。

输入描述

输入文件第一行包含三个整数 L，N，ML，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。

接下来 NN 行，每行一个整数，第 ii 行的整数 Di（0<Di<L）Di​（0<Di​<L）表示第 ii 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

其中，0≤M≤N≤5×104，1≤L≤1090≤M≤N≤5×104，1≤L≤109。

更新：数据于 2024 年 10 月 15 日进行了加强。

输出描述

输出只包含一个整数，即最短跳跃距离的最大值。

输入输出样例

示例

输入

25 5 2
2
11
14
17
21

输出

4

#include<bits/stdc++.h>
using namespace std;
int l,n,m;
const int N = 5e4+10;
int a[N];
bool check(int mid){
    int pos = 0;
    int temp = m;
    for(int i = 1;i<=n+1;i++){
        if(temp<0) break;
        //最短跳跃距离尽可能长
        if(a[i]-pos<mid){
            temp--;//移走一个
        }
        else{
            pos = a[i];
        }
    }
    if(temp<0) return true;
    return false;
}
int main(){
    cin>>l>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    a[n+1] = l;
    int L = 1,R = 1e9+10;
    while(L<R){
        int mid = (L+R+1)/2;
        if(check(mid)) R = mid - 1;
        else L = mid;
    }
    cout<<R<<endl;
    return 0;
}

例题二（lanqiao OJ 3683）

问题描述

肖恩有一大片农田，农田中有 NN 个可以种植苹果树的位置。这些位置都分布在一条直线上，坐标是 x1,x2,⋯,xNx1​,x2​,⋯,xN​ 。肖恩得到了 MM 个树苗，需要种到农田中的对应位置。

我们都知道两棵苹果树种的距离如果太近的话会互相争抢养分，导致两棵苹果树都会营养不良。所以肖恩认为相邻两棵苹果树之间的最近距离越大越好，那么请你帮肖恩算算最大的最近距离是多少？

输入描述

第一行输入两个整数 NN 和 MM ，两个数字的意义和题面中描述相同。

第二行输入 NN 个数字，第 ii 个数字 xixi​ 表示第 ii 个可以种植苹果树的位置。

数据保证 1≤N≤105,1≤M≤N,1≤xi≤1091≤N≤105,1≤M≤N,1≤xi​≤109 。

输出描述

输出一个数字表示最大的最近距离。

样例输入

5 3
1 3 4 8 9

样例输出

3

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
long long a[N];

int check(long long mid)
{
    int res=1;//表示种树的数量 
    for(int i=2,ih=1;i<=n;i++)
    {
        if(a[i]-a[ih]<mid)//如果<，说明距离不够种树,继续 
        {
            continue;
        }
        res++;//如果>=，说明可以种一棵树 
        ih=i;//ih跳到i，i++，继续 
    }
    return res;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    long long first=0,last=a[n]+1;//从第一棵树到最后一棵树 
    while(first+1!=last)
    {
        long long mid=first+(last-first)/2;
        if(check(mid)<m) last=mid;//如果检查出<,说明 种的树不够 ,说明距离太大需要向左移，所以将last=mid；
        else first=mid;//如果等于，继续右移，看看有没有更优 ，如果大于 ,说明距离太小，种的树多了，向右移动，增大距离，减小种树的数量 
    }
    cout<<first;//优解为first 
    return 0;
}