二分常見問題

問題一: (l + r) / 2

以下 code 當 (l + r) 是負的時候會出問題，例如 l = -2, r = -1，mid 會是 (-3) / 2 = -1，可實際上要是 -2，假如是跑 r = mid，那 r 就永遠不會改變，造成無限迴圈（TLE）

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

如何解決: 我們將 mid = l + (r - l) / 2 就可以了，因為 (r - l) 一定是非負的

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

問題二: r = mid - 1

以下這個代碼會陷入死循環，比如 l = 2, r = 3 時，mid = 2，此時若 check(2) = true，會不斷地執行 l = mid 這行。這是因為當 l + r 為奇數時，我們 mid 會自動往左靠。

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

解決的辦法有兩種第一種是讓 mid 自動往右靠，也就是 (l + r + 1) / 2。第二種是改成 [l, r) 的寫法，因為 r 跟 l 不可能會差 1，除非是找到答案了，所以也就不會有上述問題。也就是像下面這樣

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