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