🔍 Binary Search

二分搜尋利用已排序資料的特性，每次將搜尋範圍縮小一半，時間複雜度從 O(n) 降到 O(log n)。

Notes:

• 不只適用於排序陣列，任何具有「單調性」的搜尋空間都可以用二分搜尋
• 注意邊界條件：left、right 的初始值，以及 mid 的計算方式
• 常見變體：找左邊界、找右邊界、在答案空間上二分

四步驟框架

寫對二分的關鍵不是背模板，而是想清楚四件事：

1. 定義搜尋空間：[left, right] 代表什麼？是陣列索引，還是「答案的可能範圍」？
2. 怎麼縮小：算 mid，根據判斷把空間切到左半或右半。
3. 結束條件：left < right 還是 left <= right？
4. 回傳什麼：mid、left，還是邊界。

fun binarySearch(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1          // 搜尋空間 [left, right] 閉區間
    while (left <= right) {            // 區間非空就繼續
        val mid = left + (right - left) / 2   // 防溢位，勿用 (left+right)/2
        when {
            nums[mid] == target -> return mid
            nums[mid] < target -> left = mid + 1   // 排除 mid，往右
            else -> right = mid - 1                // 排除 mid，往左
        }
    }
    return -1
}

邊界決策

二分最容易錯的就是邊界。記住「是否要排除 mid」這條判準：

更新寫法	含意
left = mid + 1	確定 mid 不是答案，排除它
left = mid	mid 可能仍是答案，保留它（此時 mid 要用 left + (right - left + 1) / 2 上取整，否則死迴圈）
right = mid - 1	確定 mid 不是答案，排除它
right = mid	mid 可能仍是答案，保留它

• mid = left + (right - left) / 2：避免 left + right 在大數時整數溢位，並向下取整。
• 找左邊界（第一個 >= target）用 right = mid；找右邊界（最後一個 <= target）用 left = mid 配上取整。

二分是最簡單的分治

二分搜尋本質就是分治：把問題切兩半，但每次只需要處理「確定含答案的那一半」，所以遞迴式是 T(n) = T(n/2) + O(1)，解得 O(log n)。只要搜尋空間具單調性（某條件在空間上由 false 變 true 後不再變回），就能二分——不限於排序陣列，也包括「在答案值域上二分」（如最小化最大值）。

本章深入

• 排序與搜尋總覽 (Sort & Search)：各排序演算法的複雜度、穩定性與比較排序下界。

跨倉庫導讀

• 對應理論章節：搜尋演算法