关于简单的二分问题

关于简单的二分问题

以下是几种常见二分模板

l<=r为循环条件时：

if条件为真右移左界：

while(l<=r){
        ll mid=(l+r)/2;
        if(judge(mid)) l=mid+1;
        else r=mid-1;
    }
    printf("%lld",r);//等价于l-1

此时二分答案ans为r即l-1的原因是当进入最后一次循环时，l==r，此时l和r都为最终的ans，但他还要进行一次ifelse判断，此时if条件为真，l=mid+1，因此如果要用l来表示最终的答案就要再减掉一个1

if条件为真左移右界：

while(l<=r){
        int mid=(l+r)/2;
        if(judge(mid)) r=mid-1;
        else l=mid+1;
    }
    printf("%d",r+1);//等价于l

与上面的原因相同，if为真时r减少了一个1，因而要用r表示答案的话要再加一个1，但也可以用没有变化的l