對答案二分搜

常見

使用時機

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

舉例

給定一函式 f(x)=x!f(x) = x!,我們可以觀察到 x!x! 是具有單調性的,他符合嚴格遞增的條件,此時如果要搜尋第一個小於 130130x!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;
}