C++ lower_bound 与 upper_bound 核心用法解析

upper_bound 的参数格式完全相同，仅内部判断逻辑不同。

这里几个关键参数需要留意：

• first/last：迭代器，指定查找的左闭右开区间 [first, last)。
• val：要查找的目标值。
• comp：可选参数，自定义比较函数或谓词（例如 greater<int>() 可用于降序区间）。

返回值

• 成功找到：返回指向该元素的迭代器。
• 未找到：返回 last 迭代器（即区间末尾的哨兵，不指向任何有效元素）。

实战用法

1. 判断目标值是否存在

利用 lower_bound 的特性，如果它返回的迭代器不等于 end()，且指向的元素确实等于目标值，那就说明存在。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 3, 5, 7, 9};
    int target = 5;
    auto it = lower_bound(v.begin(), v.end(), target);
    
    if (it != v.end() && *it == target) {
        cout << "目标值 " << target << " 存在" << endl;
    }
    return 0;
}

2. 统计重复元素出现次数

这是一个经典技巧。既然 lower_bound 指向第一个等于 target 的位置，upper_bound 指向第一个大于 target 的位置，那么两者之间的差值就是 target 出现的次数。

vector<int> v = {1, 3, 5, 5, 5, 7, 9};
int target = 5;

auto left = lower_bound(v.begin(), v.end(), target); // 指向第一个 5
auto right = upper_bound(v.begin(), v.end(), target); // 指向 7

int count = right - left; // 5 - 2 = 3，即 5 出现 3 次
cout << "目标值 " << target << " 出现次数：" << count << endl;

3. 在有序容器中插入元素

如果你有一个有序容器，想插入新元素并保持有序，直接用 lower_bound 找到位置即可，无需手动排序。

vector<int> v = {1, 3, 7, 9};
int insert_val = 5;

// 找到第一个 >= 5 的位置（即 7 之前），插入 5
auto pos = lower_bound(v.begin(), v.end(), insert_val);
v.insert(pos, insert_val);

// 插入后 v = {1, 3, 5, 7, 9}，仍保持升序

4. 处理降序区间

当区间为降序时，默认的比较逻辑会失效，需要传入 greater<> 作为比较函数。此时 lower_bound 的逻辑变为找第一个小于等于的值，upper_bound 变为找第一个小于的值。

vector<int> v_desc = {10, 8, 6, 4, 2, 1};
int target = 4;

// 找第一个 <= 4 的元素（降序中 lower_bound 逻辑变为'<='）
auto it_lower = lower_bound(v_desc.begin(), v_desc.end(), target, greater<int>());

// 找第一个 < 4 的元素（降序中 upper_bound 逻辑变为'<'）
auto it_upper = upper_bound(v_desc.begin(), v_desc.end(), target, greater<int>());

cout << "降序中 >=4 的第一个元素：" << *it_lower << endl; // 输出：4
cout << "降序中 >4 的第一个元素：" << *it_upper << endl; // 输出：2

掌握这两个函数，配合 STL 容器，能让你的二分查找逻辑既简洁又健壮。记得，有序是前提，自定义比较器是进阶必备。