二分查找 (Binary Search)#

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

三大前置條件#

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

基本模板#

fun binarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2  // 避免整數溢位

        when {
            arr[mid] == target -> return mid
            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 次比較！

面試題：求平方根 ^↗#

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

fun mySqrt(x: Int): Int {
    if (x < 2) return x

    var left = 1
    var right = x / 2

    while (left <= right) {
        val mid = left + (right - left) / 2
        // 用除法比較，避免 mid * mid 溢位（見下方警告）
        when {
            mid == x / mid -> return mid
            mid < x / mid  -> left = mid + 1
            else           -> right = mid - 1
        }
    }

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

整數溢位風險

若直接寫 mid * mid，當 mid 很大時，兩個 Int 相乘會溢位（在 JVM 上 wrap 成負數），比較結果就錯了。兩種解法：

1. 用 Long 相乘：mid.toLong() * mid
2. 改用除法比較：mid <= x / mid（上面的寫法）

牛頓迭代法（進階）#

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

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

fun mySqrtNewton(x: Int): Int {
    if (x < 2) return x

    var r = x
    while (r.toLong() * r > x) {
        r = (r + x / r) / 2
    }

    return r
}

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

二分查找的變體#

找到目標後不立即返回，而是繼續收縮邊界，就能解出這些常見進階問題：

其中 lower bound（第一個 ≥ target 的位置）是最泛用的模板，值得單獨記住：

// 回傳第一個 arr[i] >= target 的索引；若都比 target 小，回傳 arr.size
fun lowerBound(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.size  // 半開區間 [left, right)

    while (left < right) {
        val mid = left + (right - left) / 2
        if (arr[mid] < target) {
            left = mid + 1   // mid 太小，排除
        } else {
            right = mid      // mid 可能就是答案，保留
        }
    }

    return left  // left == right，即臨界位置
}

二分查找的工程陷阱#

二分查找的概念人人都懂，但正確實作出來卻意外地難。有研究讓一群專業工程師當場手寫二分查找，結果約九成的人寫出了帶有 bug 的版本——而且這些 bug 往往在簡單測資下還能通過，要到極端輸入才會爆。

三個經典陷阱，每一個都曾在真實程式碼裡造成事故：

整數溢位#

最常見的寫法是取中點：

val mid = (low + high) / 2  // 危險！

當 low 與 high 都很大時，low + high 可能超過 Int 上界而溢位成負數，導致索引錯誤甚至陣列越界。

Kotlin 的 Int 是 32 位定長整數，low + high 一旦超過約 21 億就會 wrap 成負數——這在 JVM 上是真實會踩的雷（不像 Python 的整數是任意精度）。養成下面的習慣，跨語言都安全。

正解是先算差值再加回去，永遠不會溢位：

val mid = low + (high - low) / 2  // 安全

這不是教科書上的假想問題。JDK 早期的 Arrays.binarySearch 就因為 (low + high) / 2 而帶有溢位 bug，這個錯誤潛伏了將近十年才被發現修正。連標準函式庫都會踩，可見其隱蔽。

無窮迴圈#

更新邊界時，如果把 low = mid + 1 寫成 low = mid，可能讓區間永遠無法縮小：

// 錯誤示範：當 low 與 high 相鄰時，mid 恆等於 low
while (low < high) {
    val mid = low + (high - low) / 2
    if (check(mid)) {
        high = mid
    } else {
        low = mid   // BUG：mid 算出來還是 low，永遠卡住
    }
}

正解：把已經排除的那一側「跨過去」，確保每一輪區間都嚴格縮小——能用 mid 的一側保留 mid，另一側必須 mid + 1 或 mid - 1。

邊界條件#

下列輸入最容易被漏測，務必逐一驗證：

正確寫對的方法：先想「迴圈不變式」#

與其先把程式寫出來再靠試錯一個個補洞，不如反過來：先明確寫下迴圈不變式（loop invariant），再據此推導每一步該怎麼寫。

迴圈不變式是一句「每一輪迴圈開始與結束時都必須為真」的斷言。對標準二分查找，它是：

若目標存在於原陣列中，則它必定落在 [low, high] 這個閉區間內。

有了這句話，三件事就被它釘死了：

1. 初始化：一開始 low = 0、high = size - 1，涵蓋整個陣列，不變式自然成立。
2. 維持：每次比較後，被排除的那一側「確定不含目標」，所以可以安全跨過——這正是 mid + 1 / mid - 1 的來源。
3. 終止：每一輪區間都嚴格縮小，不可能無窮迴圈；當區間為空時，不變式告訴我們「目標不在任何地方」，即可回傳未找到。

先寫不變式，再寫迴圈——這樣 < 還是 <=、mid 還是 mid + 1，都不再是憑感覺猜，而是從不變式邏輯地推出來的。

兩組最容易寫錯的選擇，判準其實只有一條：中點 mid 有沒有可能就是答案？

記住一句話：只要某一側用了 left = mid（保留 mid），另一側就一定要用會跨過 mid 的更新（right = mid - 1），否則區間縮不下去就會無窮迴圈。

二分不只用來查值：在「答案空間」上二分#

二分查找的本質不是「在陣列裡找數字」，而是「在一個有單調性的空間上，用 O(log n) 次猜測逼近臨界值」。很多最佳化問題——求最小可行值或最大可行值——都能套用：

1. 不在陣列上二分，而是在答案的數值範圍上二分；
2. 猜一個答案 x；
3. 用一個 O(n) 的判定函式 check(x) 檢查「答案取 x 是否可行」；
4. 依結果縮小範圍，逼近那個臨界的答案。

之所以能二分，是因為可行性具有單調性：若 x 可行，則所有比它更寬鬆的值也可行；於是「可行 / 不可行」之間存在一條清楚的分界線，正是二分要找的臨界點。

識別訊號：當題目要求「最小化最大值」「最大化最小值」或「求滿足某條件的臨界值」時，多半可以「二分答案」。看到這類措辭，先別急著想複雜的貪心或 DP，先問自己：「給定一個答案 x，我能不能用一趟 O(n) 判斷它可不可行？」可以的話，就能二分。

代表題：Koko 吃香蕉 ^↗（求最小吃速）、切木頭 / 分割陣列 ^↗（最小化最大子段和）。以 Koko 吃香蕉為例——給定一堆香蕉與時限 h 小時，求能吃完的最小每小時速度：

fun minEatingSpeed(piles: IntArray, h: Int): Int {
    // 答案範圍：速度至少 1，最多等於最大那堆（再快也沒意義）
    var low = 1
    var high = piles.max()

    // 在「速度」這個答案空間上二分，找最小可行速度
    while (low < high) {
        val mid = low + (high - low) / 2
        if (canFinish(piles, mid, h)) {
            high = mid       // mid 可行，可能還能更小 → 保留 mid
        } else {
            low = mid + 1    // mid 太慢，排除 → 跨過 mid
        }
    }

    return low  // low == high 時即為最小可行速度
}

// 判定函式：以速度 speed 吃，是否能在 h 小時內吃完
private fun canFinish(piles: IntArray, speed: Int, h: Int): Boolean {
    var hours = 0L
    for (p in piles) {
        hours += (p + speed - 1) / speed  // 每堆向上取整
    }
    return hours <= h
}