二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
Q:二分能干什么呢？
1.比如：给你一个单调函数的解析式
例如y=x3+lnx+2(x-10)求函数的零点
函数是单调性 我们可以通过二分对暴力枚举进行优化
这样时间复杂度就从O(n)降到了O(logn)
2.比如：算许多东西最小值的最大化也可以用到二分
我们可以二分最终的答案，最终判断是否可行
3.比如：很难直接算出答案，但是很好判定答案合不合法
二.代码while(r-l>eps)//控制精度
{
mid=(l+r)/2;
if(f(mid)>0) r=mid;
else l=mid;
}
派
（并不知道题目来源
题面：
我的生日要到了！根据习俗，我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。
我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。
请问我们每个人拿到的派最大是多少？每个派都是一个高为1，半径不等的圆柱体。
分析
很显然这是一道二分的例题所以我们可以用二分
如果我们直接去求每个人最大派并不好求，但给定一个派的大小判断是否能够分给F个人是比较简单的
我们用f(x)表示派的大小为x的时候可以分给多少人，我们对x进行二分，判断f（x)是否能分给F个人。
最大化最小值
题面：
•把一个包含n个正整数的序列划分为m个连续的子序列(每个正整数恰好属于一个序列)。设第i个序列的各数之和为S(i)，你的任务是让所有S(i)的最大值尽量小。
•例如序列1 2 3 2 5 4划分成3个序列的最优方案为1 2 3|2 5 |4，其中S(1)、S(2)、S(3)分别为6、7、4，最大值为7；如果划分成1 2|3 2|5 4，则最大值为9，不如刚才的好。
•n<=106，所有数之和不超过109。
分析:
同样采用二分的策略，二分最小的最大值
这个值是每一段总和的上限
然后贪心，只要总和在这个限度内就不断地往里添加后面的数，直到不能添加为止，那么这些数就组成了一段
扫完所有的数之后，看一看划分出了几段
如果段数>m，说明这个最大值设得太小了，应该变大,l=mid+1
否则说明最大值还有可能变小，r=mid
排干水塘
题面：
公园里有n个水塘，需要把这n个水塘中的水排干，水塘中的水在自然条件下1个单位的时间可以蒸发A升水。现在买了1台抽水机，使用抽水机可以让你用1个单位的时间使每个水塘除开自然蒸发的A升水外，还可抽B升水，但在1个单位的时间内只能对1个水塘使用。
要你求出排干所有水塘的最少时间（水塘中的水为0时为排干）。
分析：
二分最后要求的时间T
你可以视为每个池塘先蒸发了A*T升水，之后就不再蒸发，然后你开始使用抽水机
我们可以在O(N)时间内算出用抽水机抽完剩下的水要花多少时间
如果时间>T，说明时间不够，T应该放大
否则说明时间可能更小
序列积第n小元素
题面:
给出两个长度为n的数组A和B, 在A和B中各任取一个, 可以得到n×n个积. 求第n小的元素。n<=100000
分析
我们二分答案，首先确定一个最终答案成绩x并判断是否可行
确定好x后我们从小到大枚举ai，查找有多少个x/ai<bj,统计有多少bj小于x/ai，累加入答案。再去寻找下一个ai进行同样的造作。若最后累加的答案等于n，则我们枚举的x就是正确答案
时间复杂度为O((n^2)log n)
优化
由于我们的ai是从小到大枚举的并且b数组也是有序的，也就是说bj会越来越小，我们再去枚举bj就只需要从上一次枚举到的位置开始往下枚举，找到第一个可行的bj就可以。
时间复杂度(O(n log n))
bool check(int x){
int cnt = 0;//计数器
int j = n;
for(int i = 1;i <= n;i++){
while(j>0&&b[j]*a[i]>x)j--;
cnt+=j;
}
return cnt>=m
}
跳石头
老早以前听神仙姐姐zay讲过了qwq
二分最终答案即可
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int L,N,M;
int d[500005];
bool check(int x){
int num=0,last=0;
for(int i=1;i<=N+1;i++){
if(d[i]-d[last]<x){
num++;
//cout<<i;
}
else last=i;
}
//if(d[N]-d[last]<x)num--;
//cout<<x<<" "<<num<<endl;
if(num>M)return false;
else return true;
}
int erfen(){
int l=1,r=L,mid,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(check(mid))l=mid+1,ans=mid;
else r=mid-1;
}
return ans;
}
int main(){
scanf("%d%d%d",&L,&N,&M);
for(int i=1;i<=N;i++){
scanf("%d",&d[i]);
}
d[N+1]=L;
cout<<erfen();
}
poj 2976Dropping tests
分析
大意是：给你一个价值a[i]和代价b[i]，然后我们选举n-k个物品，使得总价值/总代价。
我们二分最后答案x，只需要判定是否存在一些物品使得
部分代码
bool check(int x){
for(int i = 1;i <=n ;i++)
c[i] = a[i] - b[i]*x;
sort(c+1,c+n+1);
int sum = 0;
for(int i = 1;i <= k;i++){
sum+=c[i];
}
return sum<=0;
}
int main(){
int l,r,ans;
while(l<=r){
int mid = l+r>>1;
if(check(mid))ans = mid,r=mid-1;
else l = mid+1;
//这种写法直接记录下来答案不需要判断ans=l+1还是l-1
}
}
poj2728 Desert King
给出一个n个点的完全图，每条边都有两个权值cost和len 求一个生成树使(frac{sum costi}{sum len i}) 最小
同上题一样也是01分数规划 大致思路一样，check数组稍有变化
嗯，不写了。