很少有演算法能像二分搜尋這樣回報清晰的思考：寥寥數行程式碼，就能把 O(n) 的掃描變成 O(log n) 的搜尋，把解法從可怕的「超出時間限制」判定中拯救出來。
如果你的孩子正向著像 USA Computing Olympiad 這樣的競賽攀登，二分搜尋是首批值得掌握的技巧之一。它出現得極其頻繁，實作起來很快，還能培養強手隨處依賴的一種習慣：發現問題中的結構並加以利用。在 BIAA，我們把它視為競賽程式設計路線中的一項基礎工具。
核心思想：在有序、單調的空間中搜尋
經典的二分搜尋是在有序陣列中尋找某個值。你維護一個下界和上界，查看中間元素，並捨棄不可能包含目標的那一半。每一步都把搜尋空間減半，因此在一百萬個元素中找到答案只需大約二十次比較。
使頂尖選手脫穎而出的更深層洞見在於：二分搜尋其實並不真正需要陣列。它適用於任何單調謂詞——一個是/否的問題，其答案在你沿著有序範圍移動時恰好翻轉一次。如果某個候選值可行，那麼它一側的所有值也都可行；如果它不可行，那麼另一側的所有值也都不可行。這唯一的一次翻轉，正是二分搜尋所追尋的邊界。
每當一個問題要求找出可行的最小值，或仍然能滿足的最大值時，就問問可行性是否單調。如果是，二分搜尋通常就是出路。
對答案進行二分
這是贏下最多競賽題目的模式，然而初學者卻很少能辨識出它。你不是在資料中搜尋，而是在可能的答案中搜尋。
假設一道題要求找出使配送能在截止時間內完成所需的最小運力。直接計算這個運力可能很難。但檢驗單個猜測——「運力為 X 時，我們能否按時完成？」——往往透過貪婪掃描或快速模擬就很容易做到。而且可行性是單調的：如果運力 X 可行，任何更大的運力也可行。於是你在可能的運力範圍上做二分搜尋，並在每個中點處執行你的可行性檢驗。
這套套路很可靠：
- 確定數值答案空間（可以是整數或實數）。
- 撰寫一個回傳真或假的
check(x)函式，要快到足以反覆呼叫。 - 確認
check在該空間上是單調的。 - 二分搜尋答案發生變化的那個邊界。
這種「先猜測，再驗證」的分解方式，在奧林匹克數學中同樣出現，在那裡，給答案定界並證明其可行性是一種標準策略。
先用函式庫，再學 bug
在 C++ 中，標準範本庫已經提供了久經考驗的輔助函式。lower_bound 回傳第一個大於或等於目標值的元素位置；upper_bound 回傳第一個嚴格大於目標值的位置；而 binary_search 只是回報是否存在。優先使用這些函式可以避免許多自找的錯誤，在競賽壓力下也寫得更快。
當你必須手寫迴圈時——做對答案的二分時你就得手寫——三類 bug 導致了大多數隱藏測試失敗：
- 中點處的溢位。寫成
mid = (low + high) / 2可能使定長整數溢位。這在 Java 的標準函式庫中曾是一個真實存在的缺陷，多年未被發現，直到 2006 年才修復。請優先使用mid = low + (high - low) / 2。 - 無窮迴圈。不一致地更新邊界——例如在不變式期望
mid - 1時卻設定high = mid——可能使迴圈永遠停滯。 - 差一錯誤。混淆
while (low < high)和while (low <= high)可能悄無聲息地跳過第一個或最後一個元素。
如何練習
從普通的有序陣列搜尋開始，然後進階到「最小化最大值」和「最大化最小值」的題目，這些幾乎總是偽裝起來的對答案二分。先做幾道，然後回看你最快出錯的提交，找出你遺漏的邊界模式。在認真嘗試之後再閱讀題解，比直接冷讀題解更能培養這種辨識能力。
請注意，各項競賽的賽制、組別和參賽資格各不相同，且會隨時間變化，因此在報名前請務必在每項競賽的官方網站上確認最新詳情。
準備好把模式辨識轉化為排名成績了嗎？探索 BIAA 的競賽程式設計課程，透過結構化的練習與導師指導來建構這些技能。