一定要早日上岸鸭 · July 16, 2021 0

二分模板

「二分」模板其实有两套,主要是根据 check(mid) 函数为 true 时,需要调整的是 l 指针还是 r 指针来判断。

当 check(mid) == true 调整的是 l 时:计算 mid 的方式应该为 mid = l + r + 1 >> 1

long l = 0, r = 1000009;
while (l < r) {
    long mid = l + r + 1 >> 1;
    if (check(mid)) {
        l = mid;
    } else {
        r = mid - 1;
    }
}

当 check(mid) == true 调整的是 r 时:计算 mid 的方式应该为 mid = l + r >> 1

long l = 0, r = 1000009;
while (l < r) {
    long mid = l + r >> 1;
    if (check(mid)) {
        r = mid;
    } else {
        l = mid + 1;
    }
}