二分查找是最基础的算法，其效率较高且应用广泛，但它要求表中元素按关键字单调有序排列，同样二分答案：

应用前提：

二分答案要求满足条件的答案单调
否则你就不能确定下一次查找答案所在的区间

基本思想：

在答案可能的范围内[L,R]二分查找答案，检查当前答案是否满足题目的条件要求，根据判断结果更新查找区间。
不难发现，二分查找就是在二分答案，答案所在区间为有序线性表的第一个元素到最后一个，条件即为要找的那个值。

解决四类问题

1.求最大的最小值
2.求最小的最大值
3.求满足条件的最大(小)值
4.求最靠近一个值的值

提示：注意一些题目表面上一眼看上去就像二分，但实际上仔细验证其答案并没有单调性，所以正解往往是暴力枚举。

Aggressive cows
题目描述：
农夫John建造了一个新的畜栏，其中有N个（2 <= N <= 100,000）隔间。 隔间沿直线位于位置x1，...，xN（0 <= xi <= 1,000,000,000）。

John的C（2 <= C <= N）头牛不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。 为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？
输入描述：
第1行：两个以空格分隔的整数：N和C
第2..N + 1行：第i + 1行包含整数停转位置xi
输出描述：
第1行：一个整数：最大最小距离
输入样例#:
5 3
1
2
8
4
9
输出样例#:
3
题目来源：
DreamJudge 1638

题目解析：暴力选c个点肯定超时，考虑二分答案，这个最大值的范围为[0，点的最大值-最小值]，如果能找出c个使得他们相邻的点之间的最小距离为mid，那么小于mid的答案肯定也满足要求，若不能找到，那么大于mid的答案就更不能找到

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
const int N = 1e6+10;  
int a[N], n, m;  
bool judge(int k){ //枚举间距k，看能否使任意两相邻牛  
    int cnt = a[0], num = 1;//num为1表示已经第一头牛放在a[0]牛栏中  
    for(int i = 1; i < n; i ++){ //枚举剩下的牛栏  
        if(a[i] - cnt >= k){ //a[i]这个牛栏和上一个牛栏间距大于等于k，表示可以再放进牛  
            cnt = a[i];  
            num++;//又放进了一头牛  
        }  
        if(num >= m) return true;//所有牛都放完了  
    }  
    return false;  
}  
void solve() {  
    int l = 1, r = a[n-1] - a[0];//最小距离为1，最大距离为牛栏编号最大的减去...

掌握本节内容