二分法：
一种高效查找方法，将问题搜索范围一分为二，迭代地缩小范围，直到找到目标。
二分法适用于有序的数据集合。
常见的二分类型有：
整数二分
浮点二分
二分答案
二分解题步骤：
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;
}
