雲端 Mac 上的 iOS 二分搜尋驗收：重複值與插入邊界

Q: 找不到元素時應回傳什麼？

回傳合法插入位置，範圍是零到陣列長度，包含陣列長度本身。讀取元素前，必須先確認位置小於陣列長度。

Q: 重複值應插在既有元素之前還是之後？

lower bound 回傳第一個不小於目標的位置，可插在重複值之前；upper bound 回傳第一個大於目標的位置，可插在重複值之後。

在 Windows 上完成列表邏輯後，將 Swift 程式碼放到雲端 Mac 驗收，最容易忽略的不是「能否找到元素」，而是重複值應該插在哪裡。聊天時間軸、分段刻度和有序記錄索引都可能仰賴二分搜尋；位置只要差一格，一般測試資料仍可能通過，邊界輸入卻會造成記錄遺失。以下透過獨立指令稿建立可執行的契約，不必啟動模擬器，也不依賴網路資料。

先定義兩個插入邊界

假設輸入是遞增排序的整數陣列。下界回傳第一個「大於或等於目標值」的位置，上界回傳第一個「嚴格大於目標值」的位置。兩者相減，就是目標值出現的次數。

例如，在陣列 [1, 2, 2, 4] 中搜尋 2，下界是 1，上界是 3。搜尋 5 時，兩者都回傳 4，代表應插入陣列尾端，而不是搜尋失敗。

回傳的位置可以等於陣列長度，但存取元素的索引不行。必須先檢查範圍，再讀取元素，不能拿最後一個元素的位置代替尾端插入位置。

這裡不使用 -1 作為哨兵值，也不讓函式自動排序。自動排序會掩蓋呼叫端傳入未排序資料的問題，也可能破壞記錄之間原有的順序關係。

以半開區間實作搜尋

登入雲端 Mac 後，在自己的工作目錄建立 BoundsCheck.swift。先執行 xcrun --find swift，確認工具鏈可用，再寫入以下實作。搜尋區間始終維持為 [lo, hi)，初始上界設為陣列長度。

func lowerBound(_ values: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = values.count
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if values[mid] < target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

func upperBound(_ values: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = values.count
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if values[mid] <= target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

兩個函式只有比較條件不同，但這個差異決定了重複值會落在哪一側。中點寫成 lo + (hi - lo) / 2，避免直接將兩個邊界相加。每一輪都必須縮小區間，不能把左邊界更新為 mid，否則輸入只有兩個元素時，迴圈可能無法結束。

空陣列不需要特殊分支：迴圈不會執行，直接回傳零即可。不要為了處理空陣列而引入 count - 1，那會重新帶來負索引與閉區間終止條件的問題。

以線性參考實作驗收所有小型輸入

參考實作應該力求簡單，而不是再寫一份二分搜尋。將以下程式碼附加到同一個檔案，列舉長度零到六、元素值零到三的所有非遞減陣列，再檢查數值範圍內外的目標值。

func verify(_ values: [Int]) {
    for target in -1...4 {
        let lower = lowerBound(values, target)
        let upper = upperBound(values, target)
        let expectedLower =
            values.firstIndex(where: { $0 >= target }) ?? values.count
        let expectedUpper =
            values.firstIndex(where: { $0 > target }) ?? values.count

        precondition(lower == expectedLower)
        precondition(upper == expectedUpper)
        precondition(lower <= upper)
        precondition(values[..<lower].allSatisfy { $0 < target })
        precondition(values[lower...].allSatisfy { $0 >= target })
        precondition(values[..<upper].allSatisfy { $0 <= target })
        precondition(values[upper...].allSatisfy { $0 > target })
    }
}

func enumerate(_ prefix: [Int], remaining: Int, minimum: Int) {
    if remaining == 0 {
        verify(prefix)
        return
    }
    for value in minimum...3 {
        enumerate(prefix + [value],
                  remaining: remaining - 1,
                  minimum: value)
    }
}

for length in 0...6 {
    enumerate([], remaining: length, minimum: 0)
}
verify([Int.min, 0, Int.max])
precondition(lowerBound([Int.min, 0, Int.max], Int.min) == 0)
precondition(upperBound([Int.min, 0, Int.max], Int.max) == 3)

執行 xcrun swift BoundsCheck.swift，結束代碼為零代表所有斷言皆通過；若有失敗，程序會以非零狀態結束。指令稿不使用可能在最佳化建置中遭移除的一般 assert，也不要使用會停用安全檢查的編譯選項。

將結果接回業務介面

判斷元素是否存在時，先取得下界；只有位置小於陣列長度，而且對應的值等於目標值，才算命中。要取得所有重複值時，使用 lower..<upper 切片；目標值不存在時，自然會得到空切片。

維持排序與比較的一致性

如果陣列存放的是記錄，並以時間戳記排序，搜尋時也必須採用相同的時間戳記語意。排序時依時間遞增，搜尋時卻比較用來顯示的字串，即使演算法本身正確也無濟於事。

若相同時間戳記的記錄需要保留抵達順序，可以選擇在上界插入。如果還有業務優先順序，應先定義完整的排序鍵，而不是期待插入位置能代替排序規則。遞減排序的陣列不能直接沿用這裡的比較條件。

搜尋期間也應保持陣列不變。以非同步方式取得位置後再修改陣列，原先的位置可能已經失效；應在同一個隔離域內完成搜尋與插入，或針對同一份不可變快照操作。

將失敗案例整理為迴歸檢查清單

整合到專案測試時，保留三層檢查：固定的業務案例、小型陣列窮舉，以及真實記錄的排序契約。不要只判斷回傳值是否位於合法範圍內，因為範圍合法仍可能差一個位置。

涵蓋空陣列、單一元素、所有元素相同，以及目標值落在兩端之外的情況。
檢查下界左側的值是否全部小於目標值，上界右側的值是否全部大於目標值。
檢查重複值區間的長度是否等於線性統計的出現次數。
將失敗的陣列、目標值與預期位置儲存為固定案例。
在實際使用的工具鏈與編譯組態下重新執行。

窮舉小型輸入不等於證明所有整數輸入都正確，但能有系統地涵蓋重複值與區間縮小的各種路徑。日後即使改用泛型比較器，也應保留線性參考實作與分區斷言，讓最佳化建立在不變的介面契約上。

常見問題

找不到元素時應回傳什麼？