對答案二分搜

使用時機

如果題目給的是可以套進某個函式的資料，並且這些資料具有單調性，那麼我們就可以使用對答案二分搜這個技巧來解題。

舉例

給定一函式 $f(x) = x!$，我們可以觀察到 $x!$ 是具有單調性的，他符合嚴格遞增的條件，此時如果要搜尋第一個小於 $130$ 的 $x!$，我們可以透過以下程式碼求得答案。

bool check(int x) {
    if (x! < 130) { // 省略了求階乘的過程
        return true;
    }
    else {
        return false;
    }
}

int binary_search() { // 範例是使用半開半閉的二分搜，也可以使用別的二分搜實作
    int left = 1, right = n, ans;
    while (left + 1 < right) {
        int mid = (left + right) / 2;
        if (check(mid) == true) {
            left = mid;
        }
        else {
            right = mid;
        }
    }
    ans = left;
}