先上题目
在一个有序数组中，查找x所在的下标。
输入
第一行两个整数n和m。
第二行n个数，表示有序的数列。
接下来m行，每行一个整数x，表示一个询问的数。
输出
对于每个询问如果x在数列中，输出下标。否则输出-1
样例
输入 1
5 3
3 4 5 7 9
7
3
8
输出 1
4
1
-1
提示
对于100%的数据
n和m的范围[0,10^5];
x和数列中的元素范围[-10^6, 10^6];
数列中的任意两个元素都不相同。
【分析】很明显这是一道查找题，我们直接for一遍就行。但是，如果真能这样那就没有二分存在的必要了，for一遍的最坏的时间复杂度是O（m*n）,就是O(10^5 * 10^5),这。。。确定不会超时吗，所以就到了我们今天的主题二分上场了
何为二分？
二分就像他的名字，是分一半，然后再分一半……，（如图）
二分是一种分治的思想，二分查找也是。二分的工作原理就是每次取中间，然后判断+调整，
无限逼近最终答案。
当然二分的前提是得有序，无论什么，都要有序
下面是二分的伪代码
void points(){int l=1,r=n,best=-1; //左 右 答案while(l<=r) //范围 当越过范围时就是答案{int mid=(l+r)/2;if(judge()){ //条件判断l=mid+1; //逼近best=mid; //保存答案}else{r=mid-1; //逼近}}
}
没错就这么短，却步步都是精髓，也非常实用，而且他的时间复杂度是 O（log n）
整数二分经典例题
既然已经理解二分了，那就先来个二分查找助助兴
在一个有序数组中，查找x所在的下标。
输入
第一行两个整数n和m。
第二行n个数，表示有序的数列。
接下来m行，每行一个整数x，表示一个询问的数。
输出
对于每个询问如果x在数列中，输出下标。否则输出-1
样例
输入 1
5 3
3 4 5 7 9
7
3
8
输出 1
4
1
-1
提示
对于100%的数据
n和m的范围[0,10^5];
x和数列中的元素范围[-10^6, 10^6];
数列中的任意两个元素都不相同。
【分析】为什么是刚开始的题目？咳咳。。。这不重要。这是一道简单的二分查找题，而且已经给出是有序数组，所以只需套下伪代码。不过仍需注意，二分只是逼近，并不是准确，所以二分时还要看情况特判。
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5+10;
int a[N],d;
int find(int x){int l=1,r=n,best=-1;while(l<=r){ //二分int mid=(l+r)/2;//取中间if(a[mid]>=x){ //大了或等于r=mid-1; //变为前半部分best=mid; //保存}else{ //小了l=mid+1; //变为后半部分}}if(a[best]!=x) return -1; //特判，万一没有return best;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
while(m--){cin>>d;cout<<find(d)<<"\n";
}return 0;
}
第二题
给你一个有序的整数序列，有一系列的询问，每次询问给出一个整数num,你需要回答序列中第一个等于num的位置，最后一个等于num的位置，第一个大于num的位置,如果相应的位置不存在，就输出-1
输入
第一行输入一个整数n (1<=n<=100000)
第二行输入n个整数ai, (1<=ai<=100000)
第三行输入一个整数m,表示询问的个数 (1<=m<=100000)
接下来m行每行一个整数bi,(0<=bi<=100000)
输出
对于每个询问输出三个整数
样例
输入 1复制
10
1 3 5 7 7 7 7 9 10 11
6
1
0
7
8
11
12
输出 1复制
1 1 2
-1 -1 1
4 7 8
-1 -1 8
10 10 -1
-1 -1 -1
【分析】简单又不太简单的经典二分（当然如果你用STL里的 lowerbound和upperbound我也没办法），要注意，这次的逼近，得分情况了，如果是求第一个等于num，就往前逼近，求最后一个就往后逼近，第一个大于num就不要保存等于了，保存大于，且往后逼近
#include<bits/stdc++.h>
using namespace std;
const int N=100050;
int n,a[N],m,b;
int find1(int x) //找第一个等于
{int l=1,r=n,best=-1;while(l<=r){int mid=(l+r)/2;if(a[mid]>=x){r=mid-1;best=mid;}else{l=mid+1;}}if(a[best]!=x) return -1;return best;
}
int find2(int x){ //最后一个等于int l=1,r=n,best=-1;while(l<=r){int mid=(l+r)/2;if(a[mid]<=x){best=mid;l=mid+1;}else{r=mid-1;}}if(a[best]!=x) return -1;return best;
}
int find3(int x){ //第一个大于if(a[1]>x) return 1; //特殊情况if(a[n]<x) return -1;int l=1,r=n,best=-1;while(l<=r){int mid=(l+r)/2;if(a[mid]>x){ //不保存等于了r=mid-1;best=mid;}else{l=mid+1;}}return best;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>m;
while(m--){cin>>b;int k=find2(b);cout<<find1(b)<<" "<<k<<" "<<find3(b)<<"\n";
}return 0;
}
第三题（前方高能！！！）
【题目描述】
农夫 John 建造了一座很长的畜栏，它包括N(2≤N≤100,000)
个隔间，这些小隔间依次编号为x1,…,xN(0≤xi≤1,000,000,000)
. 但是，John的C(2≤C≤N)
头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢
【输入】
第一行：空格分隔的两个整数N
和C；
第二行—第N+1行：i+1行指出了xi的位置。
【输出】
一个整数，最大的最小值。
【输入样例】
5 3
1 2 8 4 9
【输出样例】
3
【提示】
把牛放在1，4，8
这样最小距离是3
。
【分析】这一题还是有难度，首先得知道怎么办，二分！为什么？我们想想暴力是不是能做，但数据范围太大，那只能二分了。然后主要不知道二分啥，那我们想想，除了二分位置，距离，这题还能二分啥，二分位置也解不出来，只能二分距离，且是最大距离，所以这题有了：
1.排序数组不能忘
2.二分最大距离
3. 无限逼近
#include<bits/stdc++.h>
using namespace std;
int n,c;
const int N=100050;
long long x[N];
bool judge(long long mid) //判断这个距离能否符合要求
{int cnt=1;long long th=x[1]; //上一个房屋for(int i=2;i<=n;i++){if(x[i]-th>=mid){ //距离是否大于midth=x[i]; //更换上一个房屋cnt++; //房屋++}}return cnt>=c; //符合要求
}
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>x[i];
sort(x+1,x+n+1); //排序
long long l=1,r=1e10,best=-1;
while(l<=r){ //二分最大距离long long mid=(l+r)/2;if(judge(mid)){ //判断l=mid+1; //可以就继续best=mid; //保存}else{r=mid-1; //距离太大，缩小}
}
cout<<best;return 0;
}
拓展浮点二分
浮点二分相比于普通二分难比较了，而且也不能加1，减1了
这里给大家整理了下注意事项
1.浮点比较得用eps（其实就是0，为了防止精度不够，通常要射，如1e-6,就是把0保留了6位小数）,或者限定次数
2.浮点二分通常用bool函数区比较，直接的话容易爆精度
3.浮点二分的精度设的大些，方爆精度的
好的有请例题
在x轴上有n个人，每个人有一个移动速度 v1,v2,v3…vn, 现在需要找一个地方让大家聚到一起开会，问你最少需要多少时间才可以让所有人都到达同一个点
输入
第一行输入一个整数n
第二行输入n个整数
x1,x2,x3…xn 表示每个人初始的位置
第三行输入n个整数
v1,v2,v3…vn表示每个人的移动速度
输出
输出一个浮点数，保留五位小数
样例
输入 1复制
3
7 1 3
1 2 1
输出 1复制
2.00000
输入 2复制
10
2 3 5 7 11 13 17 19 23 29
6 5 4 3 2 1 2 3 4 5
输出 2复制
2.75000
2≤n≤60000,1≤x i ,v i ≤10 ^ 9
【分析】这题我直接说了，是二分时间，至于为什么大家可以自己思考。二分时间的话这题就简单了
#include<bits/stdc++.h>
using namespace std;
const int N=60005;
int n,x[N],v[N];
const double eps=1e-6;
bool judge(double mid){double mi=-1e18;double mx=1e18;for(int i=1;i<=n;i++){double l=x[i]*1.0-v[i]*mid; //最小的位置double r=x[i]*1.0+v[i]*mid; //最大的位置if(l-mi>eps) mi=l;if(r-mx<-eps) mx=r;}if(mx-mi>=eps) return true;return false;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
double l=1,r=1e9,best=-1;
int step=50;
while(step--){//二分次数double mid=(l+r)/2;if(judge(mid)){r=mid-1;best=mid;}else{l=mid+1;}
}
printf("%.5f",best);return 0;
}
