二分搜尋下界/上界深度解析：lower_bound、upper_bound 與手寫實作陷阱

STL 三大二分搜尋函數

關鍵差異：下界可等於，上界必須大於

對已排序陣列 {0,0,2,2,2,4,4,4,4,5}：

• 查找 2：
  lower_bound → 指向索引 2 (第一個 2)
upper_bound → 指向索引 5 (第一個 4)
個數 = upper - lower = 3
• 查找 3 (不存在)：
  lower_bound = upper_bound = 指向索引 5 (第一個 4)，可作為插入位置。

手寫二分搜尋標準模板 (左閉右開區間 [l, r))

// lower_bound: 第一個 >= target
int lower_bound(const vector& a, int target) {
    int l = 0, r = a.size();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] < target) l = mid + 1;
        else r = mid;
    }
    return l; // 可能等於 a.size() (所有元素 < target)
}

// upper_bound: 第一個 > target
int upper_bound(const vector& a, int target) {
    int l = 0, r = a.size();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] <= target) l = mid + 1;
        else r = mid;
    }
    return l;
}

常見面試陷阱

1. 區間定義不一致：[l, r] vs [l, r) 導致邊界條件、mid 計算、更新邏輯全不同。**請固定採用一種風格** (推薦左閉右開)。
2. 回傳值語意混淆：找不到時回傳 -1? 插入位置? 最後一個 ≤ target? **必須先定義契約再寫碼**。
3. 整數溢位：mid = (l + r) / 2 可能溢位，改用 l + (r - l) / 2。
4. 死迴圈：更新邊界時未縮小區間 (如 `l = mid` 而非 `l = mid + 1`)。

實務建議

• 生產碼**直接使用 STL** (std::lower_bound 等)，經過嚴格測試、最佳化、處理邊界情況。
• 手寫僅用於教學、面試、特殊比較函數或嵌入式無 STL 環境。
• 測試案例：空陣列、單元素、全相同元素、目標小於/大於所有元素、目標在首/尾/中間。

延伸：equal_range

auto range = equal_range(v.begin(), v.end(), val); 回傳 pair<it, it>，等同 {lower_bound, upper_bound}，一次呼叫獲得完整相等區間。