二分

二分法

二分查找（Binary Search)，也叫折半查找，是用来在一个有序数组中查找某一元素的算法。

原理

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

性质

最优时间复杂度 $O(1)$ 平均与最坏时间复杂度 $O(\log n)$
空间复杂度：递归版 $O(\log n)$ 递归版（一般使用 while 循环实现） $O(1)$ 。

实现

迭代版

int binarySearch(int target){
	int l=0,r=n-1;
	while(l<r){
		int mid=(l+r)>>1,x=arr[mid];//在有符号整数中 >>1 往往比 /2 更加快速
		if(x<target){
			l = mid+1;
		}else{
			r = mid;
		}
	}
	if(arr[l]==target)	return l;
	return -1;
}

STL

STL提供了以下三种二分查找函数：

TIPS:加"[ ]"的是可选参数

binary_search(start,end,target,[compare])：在 $[start,end)$ 的范围内寻找 $target$ ，找到返回 $true$ 否则返回 $false$

upper_bound(start,end,target,[compare])
在 $[start,end)$ 的范围内寻找最后一个 $target$ ，找到返回最后一个 $target$ 的地址，否则返回 $end$ 。

lower_bound(start,end,target,[compare])
在 $[start,end)$ 的范围内寻找第一个 $target$ ，找到返回第一个 $target$ 的地址，否则返回 $end$ 。

如：

$list$ = {1,2,2,2,4,5,7,8,9,9,9}

方法	查找值	结果(为了方便，直接返回下标)
binary_search	2	true
upper_bound	2	3
lower_bound	2	1

其他

前文提到的"有序数组"的"有序"是广义的，如果一个数组中的左侧或者右侧都满足某一种条件，而另一侧都不满足这种条件，也可以看作是一种有序（如果把满足条件看做 $1$ ，不满足看做 $0$ ，至少对于这个条件的这一维度是有序的）。换言之，二分搜索法可以用来查找满足某种条件的最大（最小）的值。

二分答案

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了“二分答案”。

二分答案的步骤：

1. 确认题目能否使用二分答案（一般是求最小中的最大，最大中的最小）
2. 确定二分枚举的值（如P1182中每段和的最大值）
3. 写出check函数（检验函数），一般使用贪心等方法
4. 套用二分查找模板

例题

P1542 包裹快递

题目描述
小K成功地破解了密文。但是乘车到X国的时候，发现钱包被偷了，于是无奈之下只好作快递员来攒足路费去Orz教主……

一个快递公司要将n个包裹分别送到n个地方，并分配给邮递员小K一个事先设定好的路线，小K需要开车按照路线给的地点顺序相继送达，且不能遗漏一个地点。小K得到每个地方可以签收的时间段，并且也知道路线中一个地方到下一个地方的距离。若到达某一个地方的时间早于可以签收的时间段，则必须在这个地方停留至可以签收，但不能晚于签收的时间段，可以认为签收的过程是瞬间完成的。

为了节省燃料，小K希望在全部送达的情况下，车的最大速度越小越好，就找到了你给他设计一种方案，并求出车的最大速度最小是多少。

输入格式
第1行为一个正整数n，表示需要运送包裹的地点数。

下面n行，第i+1行有3个正整数xi，yi，si，表示按路线顺序给出第i个地点签收包裹的时间段为[xi, yi]，即最早为距出发时刻xi，最晚为距出发时刻yi，从前一个地点到达第i个地点距离为si，且保证路线中xi递增。

可以认为s1为出发的地方到第1个地点的距离，且出发时刻为0。

输出格式
仅包括一个正数，为车的最大速度最小值，结果保留两位小数。

先读题，发现是求"最大速度最小值"，明显的二分答案。我们要枚举的值明显也是这个最小的最大速度。
根据题意，可写出判断函数：

bool check(long double x){//x为当前枚举出的速度
	long double time=0;//注意精度 time为当前时间
	for(int i=0;i<n;i++){
		time += datas[i].dist / x;//距离除以速度等于时间
		if(time>datas[i].end)	return false;//如果来晚了就无法完成
	 	if(time<datas[i].start)	time = datas[i].start;//如果来早了可以等到可签收时间段
	}
	return true;//送出所有包裹，答案可行
}

再写出二分模板:

while(r-l>=1e-5){//保证精度，不漏掉可能的答案（直接l<=r或l<r可能会死循环）
	long double mid = (l+r)/2;//注意：浮点数不能使用>>1除以2
	if(check(mid)){
		r = mid;//如果当前答案可行（时间充裕）就往小枚举速度
		ans = mid;//保存最优解
	}else{
		l = mid;//否则往大枚举速度（送的太慢需要增加速度）
	}
}

完整代码：

#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
struct Data{//结构体存放地点
	int start,end,dist;
};
Data datas[200010];
int n;
long double l,r=1e9,ans;//设置r的时候不要超过有效范围
bool check(long double x){
	long double time=0;
	for(int i=0;i<n;i++){
		time += datas[i].dist / x;
		if(time>datas[i].end)	return false;
	 	if(time<datas[i].start)	time = datas[i].start;
	}
	return true;
}
int main(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> datas[i].start >> datas[i].end >> datas[i].dist;
	}
	while(r-l>=1e-5){
		long double mid = (l+r)/2;
		if(check(mid)){
			r = mid;
			ans = mid;
		}else{
			l = mid;
		}
	}
	cout << fixed << setprecision(2) << ans << endl;//注意精度要求
	return 0;
}