《算法之”浅谈二分“》

二分法是我在洛谷初次见到定义和详细解说的，但相关问题早已接触过。故分享此博客：

一、二分答案的原理和过程
1.适用范围：
当一个问题的解满足单调性（结果与询问数值成正相关或负相关）且待枚举数量，出现“最大值最小”或“最小值最大”等要求时，我们可以对答案进行二分；

2.原理:
1.在二分答案前，找出答案所在区间，即[L,R]；

2.用valid函数验证当前值的可行性；

3.迭代求解的过程中，每次计算一个mid=(L+R)/2，若valid(mid)==true时，根据单调性，选择更接近于不可能的一半区间，反之取另一半区间；

3.代码实现（以求最大值最小为例）
while ( l < r ) {
mid = ( l + r ) / 2;
if ( valid ( mid ) ) l = mid + 1;
else r=mid;
}
或

while ( l < r ) {
mid = ( l + r + 1 ) / 2;
if ( valid ( mid ) ) l = mid;
else r=mid-1;
}
4.边界问题
1.在第一种实现方式中，如果l和r为相邻的一奇一偶，则每次mid计算后都等于l，如果每次只是让l=mid或r=mid的话，会出现死循环，所以应让l=mid+1；

2.在第二种实现方式中，如果l和r为相邻的一奇一偶，则每次mid计算后都等于r，如果每次只是让l=mid或r=mid的话，会出现死循环，所以应让r=mid-1；

5.优点
1.在时间复杂度上，枚举验证从O(N)优化到O(log N);

2.在思考难度上，寻找解总是比验证解更难（NP和P的关系），所以二分答案的思考过程非常简单；
其实，我觉得，算法是无形的思考模型，在做题时，不光要找到模型，在模型之外，或许还有着其他路径！
最后，附上链接https://www.cnblogs.com/COLIN-LIGHTNING/p/8543330.html
作者的园区内有部分糕点，待有心人食用哦