二分

Keywords: #algorithm

前提条件-满足单调性

满足单调性:

✅✅✅✅✅✅❌❌❌❌ (求最大值)

❌❌❌✅✅✅✅✅✅✅ (求最小值)

不满足单调性:

✅❌✅✅✅❌ (建议直接暴力)

求最大值

例子

在✅✅✅✅✅✅❌❌❌❌中查找最大的✅

  1. $ L=1,R=10,MID=(1+10+1)/2=6 $

    ✅✅✅✅✅✅❌❌❌❌

    满足,所以 $ L=MID=6 $

  2. $ L=6,R=10,MID=(6+10+1)/2=8 $

    ✅✅✅✅✅✅❌❌❌❌

    不满足,所以 $ R=MID-1=7 $

  3. $ L=6,R=7,mid=(6+7+1)/2=7 $

    ✅✅✅✅✅✅❌❌❌❌

    不满足,所以 $ R=MID-1=6 $

因为 $ L=R $ ,所以二分结束.

code

while(l<r){
    int mid=(l+r+1)/2;
    if(check(mid)){
        l=mid;
    }
    else{
        r=mid-1;
    }
}

求最小值

例子

在❌❌❌✅✅✅✅✅✅✅中查找最小的✅

  1. $ L=1,R=10,MID=(1+10)/2=5 $

    ❌❌❌✅✅✅✅✅✅✅

    满足,所以 $ R=MID=5 $

  2. $ L=1,R=5,MID=(1+5)/2=3 $

    ❌❌❌✅✅✅✅✅✅✅

    不满足,所以 $ L=MID+1=4 $

  3. $ L=4,R=5,MID=(4+5)/2=4 $

    ❌❌❌✅✅✅✅✅✅✅

    满足,所以 $ R=4 $

因为 $ L=R $ ,所以二分结束.

code

while(l<r) {
    long long mid=(l+r)/2;
    if(check(mid)) {
        r=mid;
    } else {
        l=mid+1;
    }
}
next →