二分搜尋

🎯 什麼情境該想到我

當你「資料已排序，或某個性質具有單調性」的時候。
★ 它的難處不是概念，是邊界。 「二分搜尋很簡單但幾乎沒人第一次寫對」是業界公認的——所以這頁的重點是把三種變體的邊界寫死。

⚙️ 怎麼用（機制與模板）

基本形：找存在

func BinarySearch[T cmp.Ordered](a []T, target T) int {
    lo, hi := 0, len(a)-1          // ★ 閉區間 [lo, hi]
    for lo <= hi {                 // ★ 所以是 <=
        mid := lo + (hi-lo)/2      // ★ 不要寫 (lo+hi)/2
        switch {
        case a[mid] == target:
            return mid
        case a[mid] < target:
            lo = mid + 1
        default:
            hi = mid - 1
        }
    }
    return -1
}

三個必踩的點：

lo + (hi-lo)/2 而非 (lo+hi)/2 —— 後者在 lo、hi 都很大時會整數溢位。
★ 這是 Java Arrays.binarySearch 潛伏了九年的著名 bug（2006 年才被發現）。
Go 的 int 是 64 位元，實務上很難溢位，但寫對是免費的。
區間定義要前後一致。用閉區間 [lo, hi] 就配 lo <= hi 與 mid±1；
用半開區間 [lo, hi) 就配 lo < hi、hi = mid（不減 1）。混用就是無窮迴圈或漏解。
迴圈不變式：「如果 target 存在，它一定在 [lo, hi] 內」——每一步都要維持這件事。

★ 三種變體（實務上更常用的是後兩種）

要找什麼	名稱	Go 標準庫
某個相等的元素	基本形	—
第一個 `>= target`	lower_bound	`slices.BinarySearch`
第一個 `> target`	upper_bound	自己寫或 `sort.Search`

統一的「找邊界」模板（強烈建議只記這一個）：

// 回傳第一個讓 pred 為 true 的索引；全都 false 則回傳 len(a)
// ★ 前提：pred 必須是單調的 —— false false false true true true
func LowerBound[T any](a []T, pred func(T) bool) int {
    lo, hi := 0, len(a)            // ★ 半開區間 [lo, hi)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if pred(a[mid]) {
            hi = mid               // ★ 不減 1：mid 本身可能就是答案
        } else {
            lo = mid + 1
        }
    }
    return lo                      // lo == hi
}
 
// 第一個 >= target
i := LowerBound(a, func(v int) bool { return v >= target })
// 第一個 > target
j := LowerBound(a, func(v int) bool { return v > target })
// 區間 [i, j) 就是所有等於 target 的元素 —— ★ 計數問題一行解決

★ 只記這一個模板就夠了。
「找某個值」可以用 i := LowerBound(...) 然後檢查 i < len(a) && a[i] == target。
三種變體統一成一個，就不會再寫錯邊界。

Go 標準庫（2026-09-20 查證）：

func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool)
func BinarySearchFunc[S ~[]E, E, T any](x S, target T, cmp func(E, T) int) (int, bool)
func Search(n int, f func(int) bool) int   // sort.Search，更通用的「找邊界」

slices.BinarySearch 回傳 (位置, 是否找到)——沒找到時位置就是「該插入的地方」，正是 lower_bound。

★ 對答案二分（實務上最有價值的用法）

二分搜尋不只用在陣列上。只要「答案空間單調」，就能二分。

判斷式 f(x) 滿足： $x$ 夠大時 f(x) = true， $x$ 小時 f(x) = false（或反過來）
→ 就能二分找出那個臨界點，即使 f 本身是一個很貴的模擬。

典型應用：

「最少要幾台機器才能在 T 秒內處理完」→ 對機器數二分
「限流的速率設多少才不會超過 p99 SLO」→ 對速率二分
「切成幾段才能讓最大段 ≤ X」→ 對 X 二分
「二分部署百分比找出劣化的臨界點」

lo, hi := 1, 10000
for lo < hi {
    mid := lo + (hi-lo)/2
    if canFinishInTime(mid) {      // ★ 這裡可以是任意昂貴的檢查
        hi = mid
    } else {
        lo = mid + 1
    }
}
// lo 就是最小可行值

★ 把「求最佳值」變成「檢查某個值可不可行」 —— 這是一個很強的問題轉換技巧，
也是工具-程式面試解題套路裡值得記住的一招。

複雜度

$T (n) = T (n /2) + Θ (1) \Rightarrow Θ (lo g n)$
（主定理 Case 2， $a = 1, b = 2$ ，見分治法）

$n = 1 0^{9}$ 時只要約 30 次比較。

🧪 我實際套用的紀錄

（待填）

⚠️ 注意 / 什麼時候不適用

★ 前提是「單調」，不只是「排序」。對答案二分時，要先確認判斷式真的單調——不單調就會找到錯的答案而且不會報錯。
★ 鏈結串列上沒有意義。二分需要 $O (1)$ 隨機存取；鏈結串列取中點要 $O (n)$ ，總複雜度退化成 $O (n)$ （見鏈結串列）。
小陣列上線性掃描更快。 $n < 50$ 左右時，順序掃描的快取友善與無分支預測失誤通常勝過二分（二分的存取模式是跳躍的）。
維持排序的成本。如果資料一直在變，維持排序的代價可能超過查詢的節省——考慮雜湊表（不需要順序）或紅黑樹（動態有序）。
浮點數二分要用「固定迭代次數」而非 lo < hi，否則精度問題會造成無窮迴圈。通常跑 100 次或用 hi - lo > eps。
重複元素時要明確想清楚要哪一個——用 lower/upper bound，不要用基本形。

🔗 相關工具

分治法 —— 二分是最簡單的分治（只遞迴一邊）
二元搜尋樹 —— 動態版本：支援增刪的有序查找
雜湊表 —— 不需要順序時更快（ $O (1)$ vs $O (lo g n)$ ）
順序統計量與中位數 —— quickselect 也是「只遞迴一邊」
工具-程式面試解題套路 —— 「對答案二分」的問題轉換技巧
演算法導論

Quartz 5

Explorer