二分查找 (Binary Search)#

二分查找是最基礎且高效的查找演算法，透過每次將搜尋區間縮小一半，達到 O(log n) 的時間複雜度。

三大前置條件#

使用二分查找必須同時滿足以下三個條件：

1. 單調性 (Monotonicity)

   • 資料必須有序（遞增或遞減）
   • 無序資料只能線性查找

2. 有界性 (Bounded)

   • 必須有明確的左界與右界
   • 演算法依賴邊界的收縮

3. 支援索引存取 (Index Accessible)

   • 必須能 O(1) 時間存取任意位置
   • 陣列適合，鏈結串列不適合

基本模板#

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # 避免整數溢出

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # 未找到

背誦要點：

• while left <= right（取等號）
• mid = left + (right - left) // 2（避免溢出）
• left = mid + 1 和 right = mid - 1（不含 mid）

執行過程示例#

陣列：[10, 14, 19, 26, 27, 31, 33, 35, 42, 44] 目標：31

時間複雜度分析#

每次比較後，搜尋區間縮小一半：

$$n \rightarrow \frac{n}{2} \rightarrow \frac{n}{4} \rightarrow … \rightarrow 1$$

設經過 k 次後區間為 1：$\frac{n}{2^k} = 1 \Rightarrow k = \log_2 n$

時間複雜度：O(log n)

對於 10 億筆資料，最多只需約 30 次比較！

面試題：求平方根 (LeetCode 69)#

利用二分查找求 $\sqrt{x}$，本質是找 $t$ 使得 $t^2 \leq x < (t+1)^2$。

def mySqrt(x):
    if x < 2:
        return x

    left, right = 1, x // 2

    while left <= right:
        mid = left + (right - left) // 2
        square = mid * mid

        if square == x:
            return mid
        elif square < x:
            left = mid + 1
        else:
            right = mid - 1

    return right  # 返回不超過 sqrt(x) 的最大整數

整數溢出風險

計算 mid * mid 時可能溢出。解決方案：

1. 使用 64 位整數
2. 改用除法比較：mid > x / mid

牛頓迭代法（進階）#

更快的平方根計算方法，基於數學公式：

$$x_{new} = \frac{x_{old} + \frac{C}{x_{old}}}{2}$$

def mySqrt_newton(x):
    if x < 2:
        return x

    r = x
    while r * r > x:
        r = (r + x // r) // 2

    return r

牛頓迭代法收斂速度比二分法更快，《乾坤之錘 III》遊戲引擎中的快速反平方根演算法就是基於此原理。

二分查找的變體#

面試中常見的進階問題：

1. 查找第一個等於目標值的元素
2. 查找最後一個等於目標值的元素
3. 查找第一個大於等於目標值的元素
4. 查找最後一個小於等於目標值的元素

這些變體的關鍵在於：找到目標後不立即返回，而是繼續收縮邊界。