在C++的STL库中，lower_bound和upper_bound是用于有序序列的高效查找函数，二者均基于二分查找实现（时间复杂度O(log n)）。以下是它们的核心区别和典型应用场景：

---

1. lower_bound

• 作用：在有序区间内查找第一个**≥目标值**的元素位置
• 返回值：迭代器指向第一个符合要求的元素，若所有元素均<目标值则返回end()
• 数学表达：lower_bound(arr, x) = min{ i | arr[i] >= x }

示例：

vector<int> arr = {2,4,4,6,8,10};
auto pos = lower_bound(arr.begin(), arr.end(), 4)-data.begin();
// 返回第一个4的迭代器（索引1）

---

2. upper_bound

• 作用：在有序区间内查找第一个**>目标值**的元素位置
• 返回值：迭代器指向第一个符合要求的元素，若所有元素均≤目标值则返回end()
• 数学表达：upper_bound(arr, x) = min{ i | arr[i] > x }

示例：

vector<int> arr = {2,4,4,6,8,10};
auto pos = upper_bound(arr.begin(), arr.end(), 4)-data.begin();
// 返回第一个6的迭代器（索引3）

---

3. 对比示意图

数组：2  4  4  6  8  10
查找值：4
           ↓ lower_bound
             ↑ upper_bound
区间：[4的起始位置, 4的结束位置)

---

4. 典型应用场景

场景1：统计元素出现次数

int count = upper_bound(arr.begin(), arr.end(), x) 
          - lower_bound(arr.begin(), arr.end(), x);

场景2：插入元素保持有序性

vector<int> vec = {1,3,5,7};
auto insert_pos = lower_bound(vec.begin(), vec.end(), 6)-data.begin();
vec.insert(insert_pos, 6); // 插入后保持有序：1,3,5,6,7

场景3：范围查询

// 查找所有≥a且<b的元素
auto left = lower_bound(arr.begin(), arr.end(), a)-data.begin();
auto right = upper_bound(arr.begin(), arr.end(), b-1)-data.begin();

---

5. 注意事项

1. 前提条件：必须在有序序列（默认升序）中使用，否则结果未定义
2. 自定义排序：若序列为降序，需显式指定比较函数

   // 降序数组查找
   upper_bound(arr.rbegin(), arr.rend(), x, greater<int>());
   

3. 返回值处理：对返回的迭代器需做有效性检查，避免越界访问

---

6. 实战代码示例

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> data = {1,2,3,3,3,5,6};
    
    // 查找第一个≥3的位置
    auto lb = std::lower_bound(data.begin(), data.end(), 3)-data.begin();
    // lb指向索引2（第一个3）
    
    // 查找第一个>3的位置
    auto ub = std::upper_bound(data.begin(), data.end(), 3)-data.begin();
    // ub指向索引5（元素5）
    
    return 0;
}

理解这两个函数的微妙差异，能显著提升处理有序数据集的代码效率和准确性。