函數定義

• lower_bound(first, last, val)：返回指向**第一個 ≥ val** 元素的迭代器。
• upper_bound(first, last, val)：返回指向**第一個 > val** 元素的迭代器。

前提：範圍 [first, last) 已按非遞減序排序。

語義區別

數組：[1, 2, 2, 3, 4]
lower_bound(2) → 指向索引 1（第一個 2）
upper_bound(2) → 指向索引 3（第一個 3）

• equal_range(val) 返回 {lower_bound, upper_bound}，即 val 的所有出現區間。
• binary_search 僅返回 bool，不給位置。

手寫二分實現

// 返回第一個 >= val 的位置 [0, n)
int my_lower_bound(const vector& a, int val) {
    int l = 0, r = a.size(); // [l, r)
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] < val) l = mid + 1;
        else r = mid;
    }
    return l;
}

// 返回第一個 > val 的位置 [0, n)
int my_upper_bound(const vector& a, int val) {
    int l = 0, r = a.size();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] <= val) l = mid + 1;
        else r = mid;
    }
    return l;
}

關鍵區別

其餘情況均 r = mid。循環不變量：[0, l) 全 [r, n) 全 ≥val（或 >val）。

應用場景

• 插入位置：v.insert(lower_bound(v.begin(), v.end(), x), x) 保持有序。
• 計數：upper_bound - lower_bound 等於 val 出現次數。
• 區間查詢：[lower_bound(L), upper_bound(R)) 為值在 [L,R] 的元素範圍。
• 離散化：lower_bound(sorted_unique.begin(), sorted_unique.end(), x) - sorted_unique.begin() 得到排名。

總結

lower_bound/upper_bound 是 C++ 標準庫二分查找的核心，語義精確、性能最優。手寫時注意：

1. 區間定義：[l, r) 左閉右開。
2. 判斷條件嚴格區分 < vs <=。
3. 返回 l（或 r），循環結束時 l==r 即為答案位置。

熟練掌握兩者區別與手寫模板，是演算法競賽與工程開發的基本功。