二分
参考y总模板 常用代码模板1——基础算法
思想：
1. 确定一个区间，使得目标值一档在区间内
2. 找一个性质，满足
- 性质具有二段性（区间可以按照元素是否拥有该性质把区间分成前后两段
- 答案是二段性的分界点（对于离散的区间，如整数二分，分界点有两个，分别是左区间的右端点和右区间的左端点）
第一类：ans 是左区间右端点
/*
将区间分为 [l,mid - 1][mid,r]
如果 mid 在左区间，则 ans 可能在 mid 的右边，也可能是 mid ，（但不可能在 mid 左边）即在[mid,r]内
否则 ans 在[l,mid - 1] 内
*/
while(l < r)
{
mid = l + r + 1 >> 1;
//由于整数除法下取整，l + r >> 1 的结果可能等于 l,会产生死循环，所以要再 +1
if(check(mid)) l = mid;
else r = mid - 1;
}
第二类：ans 是右区间左端点
/*
将区间分为 [l,mid][mid + 1,r]
如果 mid 在右区间，则 ans 可能在 mid 的左边，也可能是 mid ，（但不可能在 mid 右边）即在[l,mid]内
否则 ans 在[mid + 1,r] 内
*/
while(l < r)
{
mid = l + r >> 1;
//下取整不存在 mid == r 的情况，不会出现死循环
if(check(mid)) r = mid;
else l = mid + 1;
}
AcWing 789. 数的范围
整数二分步骤
1. 找一个区间 [l,r] ，使得答案一定在区间中；
2. 找一个判断条件，使得该判断条件具有二段性，且答案一定是该二段性的分界点
3. 分析终点M在该判断条件下是否成立。如果成立，考虑答案在哪个区间；如果不成立，考虑答案在哪个区间
4. 如果更新方式是 r = mid ，则不用做任何处理；如果更新方式是 l = mid ，则需要在计算 mid 时加1
代码
AcWing 790. 数的三次方根
区间是连续的，不需要按照更新方式做特殊处理
代码
三分法
对于一组整体呈单峰函数（即凸函数或凹函数）的数据，可以采用三分法和导数二分法
- 导数二分：单峰函数的导数一般是线性函数，可以二分，具体代码就是对数据的差分数组进行二分
- 三分：取三等分点 ml,mr，
- 对于向上凸的函数，
- 如果 ml <= mr ，则左端点可以更新为 ml
- 如果 mr > ml ，则右端点更新为 mr
- 对于向上凹的函数则反之
