Binary Search 二元搜索法
- 通常一般的二分搜是在解決以下這種問題：如果有一個遞增的函數 f 定義在區間
[a,a+n) 上，請求出滿足 f(s)≥c的最小整數s。
- 若用一般的 linear search 從 a 開始搜直到找到滿足條件的 s，那麼複雜度是 O(n)，而用二元搜索法可以優化時間複雜度變成 O(logn)。
想法是對於某個在 (a,a+n) 中的整數 k，如果 f(k−1)≥c，那麼 s<k，也就是答案會落在區間 [a,k) 中。
反之，如果 f(k−1)<c，那麼 s≥k，也就是說你要求的答案會落在 [k,a+n)。
為了讓兩種情況的可能性都盡量低， k 取愈接近 a + n/2 愈好。如此一來，每次候選區間的長度都會縮小一半，因此複雜度為 O(logn)。
- 實務上，這種函數 f 常常不能直接得出某一點的值 f(a)（甚至只能確認它和 c 的大小關係），而需要 O(M) 的時間來計算。顯然地，這時複雜度是 O(Mlogn)。
1. 三元搜
- 利用二分搜這種「縮短候選人長度」的想法，我們可以找出滿足特定性質的函數的最小值，這種技巧稱為三分搜。
- 三分搜處理的問題如下：有一個在 [a,a+n) 中先嚴格遞減再嚴格遞增的函數 f，請求出 f 在 [a,a+n) 的最小值。取在 [a,a+n) 中的兩個整數 x<y。如果 f(x)<f(y)，那麼最小值一定落在 [a,y)。如果 f(x)>f(y)，那麼最小值一定落在 (x,a+n)。如果 f(x)=f(y)，那麼最小值一定落在 (x,y)。為了讓候選區間每次都會縮短一定的比例，通常都取 x 跟 y 為區間的三等分點（取中間一點的話常數會變小）。複雜度仍然是 O(logn)。
2. 對答案二分搜
- 有許多問題都喜歡叫你求「滿足條件的最小值」這種東西。如果這個問題滿足「單調
性」，那或許可以考慮對答案二分搜。
- 什麼是「單調性」呢？考慮一個函數 P，如果 s 滿足條件，那麼 P(s) = 1，反之則為 0。如果 P 有單調性，我們就說這個問題有單調性。這樣的好處是，我們可以直接用前面的方法二分搜出要求的 s。如果計算 P 的複雜度並不大時，這樣的方法可以有非常的表現效率。在你沒辦法快速求出 s 而只能快速確認一個 s 是否符合條件時，這是一個非常好的方法。
- 以此題而言，
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;
}