二分

二分查找：在一个已知的有序数据集上进行二分地查找
二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案

模板

模板 1：

while (l < r)
{
	int mid = l + r >> 1;	//(l+r)/2
	if (check(mid))  r = mid;    // check()判断mid是否满足性质
	else l = mid + 1;
}

模板 2：

while (l < r)
{
	int mid = l + r + 1 >> 1;	//(l+r+1)/2
	if (check(mid))  l = mid;
	else r = mid - 1;
}

第一个模板是尽量往左找目标，第二个模板是尽量往右找目标。 ###### 模板 3：（浮点二分）

while(r-l>1e-5) //需要一个精度保证
{
	double mid = (l+r)/2;
	if(check(mid)) l=mid; //或r=mid;
	else r=mid; //或l=mid;
}

二分查找

例1—— 查找

例 2—— A-B 数对

例 3—— 烦恼的高考志愿

例 4—— 银行贷款

练习 ：

整数二分 ：
###### 1、 数的范围
###### 2 、 砍树
实数二分：
###### 3 、 数的三次方根
###### 4 、 一元三次方程求解

二分答案

什么是二分答案？

答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。
判断：根据题意写个 check 函数，如果满足 check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间）。一直往复，直至到最终的答案。 ##### 如何判断一个题是不是用二分答案做?

• 答案在一个区间内（一般情况下，区间会很大，暴力超时）
• 直接搜索不好搜，但是容易判断一个答案可行不可行
• 该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。

此外，可能还会有一个典型的特征：求...最大值的最小 、 求...最小值的最大。
1、求...最大值的最小，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让 r=mid），对应模板 1；
2、同样，求...最小值的最大 时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让 l=mid），对应模板 2；

例 1—— 木材加工

例 2—— 跳石头

例 3—— 丢瓶盖

例 4—— 数列分段 Section II

练习 ：

1 、进击的奶牛

2 、路标设置

3 、最佳牛围栏

4 、kotori 的设备