二分答案（求最大值的最小值||求最小值的最大值）

引入

二分答案要建立在二分查找的基础上，在此之前，要知道二分查找的三个模板

• 模板一

while(l<r)
{
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
}
1
2
3
4
5
6

• 模板二

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

• 模板三

while(r-l<1e-5)
{
        double mid = (l+r)/2;
        if(check(mid)) l=mid; //或r=mid;
        else r=mid; //或l=mid;
}
1
2
3
4
5
6

正文

二分查找是建立在一个单调性的范围内，三分是二分求导以后单调，即求极值，二分答案是答案在具有一定的单调性，所以二分答案只有两个要做的事情，一是选择模板，二是写check函数，具体内容具体分析

如何选择模板？

求…最大值的最小 、 求…最小值的最大。
1、求…最大值的最小，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让r=mid），对应模板1；
2、同样，求…最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让l=mid），对应模板2；