3.1 算法解釋

二分搜尋 也常被稱為 二分法 或 折半搜尋 (binary search, bisect)，每次搜尋時通過將待搜尋的單調區間分成兩部分並只取一部分繼續搜尋，將搜尋的複雜度大大減少。對於一個長度為 $O(n)$ 的陣列，二分搜尋的時間複雜度為 $O(\log n)$。

舉例來說，給定一個排好序的陣列 $\{3,4,5,6,7\}$，我們希望搜尋 4 是否在這個陣列中。第一次折半時考慮中位數 5，因為 5 大於 4，所以如果 4 存在於這個陣列，那麼它必定存在於 5 左邊這一半。於是我們的搜尋區間變成了 $\{3,4,5\}$。（注意，根據具體情況和您的解題習慣，這裡的 5 可以保留也可以不保留，這並不影響時間複雜度的等級。）第二次折半時考慮新的中位數 4，正好是我們需要搜尋的數字。於是我們發現，對於一個長度為 5 的陣列，我們只進行了 2 次搜尋。如果是遍歷陣列，最壞情況則需要搜尋 5 次。

我們也可以用更數學化的方式定義二分搜尋。給定一個在 $[a, b]$ 區間內的單調函數 $f(t)$，若 $f(a)$ 和 $f(b)$ 正負性相反，那麼必定存在一個解 $c$，使得 $f(c) = 0$。在上述例子中，$f(t)$ 是離散函數 $f(t) = t + 2$，搜尋 4 是否存在等價於求 $f(t) - 4 = 0$ 是否有離散解。因為 $f(1) - 4 = 3 - 4 = -1 < 0$、$f(5) - 4 = 7 - 4 = 3 > 0$，且函數在區間內單調遞增，因此我們可以利用二分搜尋求解。如果最後二分到了不能再分的情況，如只剩一個數字，且剩餘區間裡不存在滿足條件的解，則說明不存在離散解，即 4 不在這個陣列中。

具體到代碼上，二分搜尋時區間的左右端取開區間還是閉區間在絕大多數情況下都可以，因此有些初學者會容易搞不清楚如何定義區間開閉性。這裡提供兩個小訣竅：第一是嘗試熟練使用一種寫法，比如左閉右開（滿足 C++、Python 等語言的習慣）或左閉右閉（便於處理邊界條件），盡量只保持這一種寫法；第二是在解題時思考如果最後區間只剩下一個數或者兩個數，自己的寫法是否會陷入死循環，如果某種寫法無法跳出死循環，則考慮嘗試另一種寫法。

二分搜尋也可以看作雙指針的一種特殊情況，但我們一般會將二者區分。雙指針類型的題，指針通常是一步一步移動的，而在二分搜尋中，指針通常每次移動半個區間長度。