Binary Search 二元搜索法

  • 通常一般的二分搜是在解決以下這種問題:如果有一個遞增的函數 ff 定義在區間 [a,a+n)[a, a + n) 上,請求出滿足 f(s)cf(s)\ge c的最小整數ss
  • 若用一般的 linear search 從 a 開始搜直到找到滿足條件的 s,那麼複雜度是 O(n)O(n),而用二元搜索法可以優化時間複雜度變成 O(logn)O(\log n)
    想法是對於某個在 (a,a+n)(a, a + n) 中的整數 kk,如果 f(k1)cf(k − 1) \ge c,那麼 s<ks < k,也就是答案會落在區間 [a,k)[a, k) 中。
    反之,如果 f(k1)<cf(k − 1) < c,那麼 sks \ge k,也就是說你要求的答案會落在 [k,a+n)[k, a + n)
    為了讓兩種情況的可能性都盡量低, k 取愈接近 a + n/2 愈好。如此一來,每次候選區間的長度都會縮小一半,因此複雜度為 O(logn)O(\log n)
  • 實務上,這種函數 ff 常常不能直接得出某一點的值 f(a)f(a)(甚至只能確認它和 cc 的大小關係),而需要 O(M)O(M) 的時間來計算。顯然地,這時複雜度是 O(Mlogn)O(M \log n)

1. 三元搜

  • 利用二分搜這種「縮短候選人長度」的想法,我們可以找出滿足特定性質的函數的最小值,這種技巧稱為三分搜。
  • 三分搜處理的問題如下:有一個在 [a,a+n)[a, a + n) 中先嚴格遞減再嚴格遞增的函數 ff,請求出 ff[a,a+n)[a, a + n) 的最小值。取在 [a,a+n)[a, a + n) 中的兩個整數 x<yx < y。如果 f(x)<f(y)f(x) < f(y),那麼最小值一定落在 [a,y)[a, y)。如果 f(x)>f(y)f(x) > f(y),那麼最小值一定落在 (x,a+n)(x, a + n)。如果 f(x)=f(y)f(x) = f(y),那麼最小值一定落在 (x,y)(x, y)。為了讓候選區間每次都會縮短一定的比例,通常都取 x 跟 y 為區間的三等分點(取中間一點的話常數會變小)。複雜度仍然是 O(logn)O(\log n)

2. 對答案二分搜

  • 有許多問題都喜歡叫你求「滿足條件的最小值」這種東西。如果這個問題滿足「單調 性」,那或許可以考慮對答案二分搜。
  • 什麼是「單調性」呢?考慮一個函數 P,如果 s 滿足條件,那麼 P(s) = 1,反之則為 0。如果 P 有單調性,我們就說這個問題有單調性。這樣的好處是,我們可以直接用前面的方法二分搜出要求的 s。如果計算 P 的複雜度並不大時,這樣的方法可以有非常的表現效率。在你沒辦法快速求出 s 而只能快速確認一個 s 是否符合條件時,這是一個非常好的方法。

例題:Leetcode875. Koko Eating Bananas

  • 以此題而言, canFinish 就是一個具備單調性的函式,符合我們對答案作二分搜的條件。
int minEatingSpeed(vector<int>& piles, int h) {
    int max = *max_element(piles.begin(), piles.end());
    if (piles.size() == h)
        return max;
    int left = 1, right = max + 1;
    while (left < right){
        int mid = left + (right-left)/2;
        if (canFinish(piles, mid, h)){
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

bool canFinish(vector<int> piles, int speed, int h){
    int time = 0;
    for (int n : piles){
        time += n/speed + ((n % speed > 0) ? 1 : 0);
    }
    return time <= h;
}