2026-03-10 • C++ • ~5 min read

C++ STL中lower_bound()和upper_bound()函数

查找操作是程序中最常见的需求之一。如果面对一个无序的数组，我们只能通过线性扫描逐个比对，时间复杂度为 O(n)，效率低下。然而，当数据已经有序时，我们可以借助更高效的算法实现"精准定位"。C++ 标准模板库（STL）为此提供了两个强大的工具：std::lower_bound() 和 std::upper_bound()。

这两个函数均基于二分查找机制实现，能够在 O(log n) 时间内完成查找任务，极大地提升了性能。相较于手动编写二分逻辑，使用 STL 提供的版本不仅代码更简洁，而且经过高度优化，行为定义明确，不易出错。

基本定义与语法

lower_bound()和upper_bound()的标准函数原型如下：

// lower_bound 原型
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val);

template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

// upper_bound 原型
template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val);

template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

其中各参数含义如下：

first, last：构成一个左闭右开区间 [first, last)，表示待搜索的范围。
val：要查找的目标值。
comp：可选的比较函数对象，用于自定义排序规则。

函数返回一个迭代器。若成功找到符合条件的元素，则指向该位置；否则返回 last，表示目标应插入的位置。值得注意的是，这两个函数要求输入区间必须已按相应规则排序，否则结果未定义。

功能差异对比

尽管 lower_bound 和 upper_bound 都用于在有序序列中定位边界，但它们的语义存在关键区别：

特性	lower_bound	upper_bound
查找条件	第一个 ≥ val 的元素	第一个 > val 的元素
插入语义	可插入而不破坏顺序的最小位置	可插入而不破坏顺序的最大位置
目标不存在时	返回首个大于 val 的位置	返回首个大于 val 的位置

以数组 {1, 2, 4, 4, 4, 6, 7} 为例，查找值 4：

lower_bound 返回指向第一个 4 的迭代器（索引 2），因为它满足"不小于"条件。
upper_bound 返回指向 6 的迭代器（索引 5），因为它是第一个严格大于 4 的元素。

由此可见，两者共同圈定了值 4 在数组中的完整范围 [2, 5)，即所有等于 4 的元素都位于此区间内。

工作原理

lower_bound 和 upper_bound 的底层均采用二分查找策略，维护一个动态变化的搜索区间。其核心在于比较逻辑的不同。

对于 lower_bound，算法目标是找到最小下标 i 满足 arr[i] >= value。伪代码如下（为迭代器运算）：

while (first < last) {
    auto mid = first + (last - first) / 2;
    if (*mid < value)
        first = mid + 1;  // 当前值太小，答案在右半区
    else
        last = mid;       // 当前值足够大，保留作为候选
}
return first;

而对于 upper_bound，目标是找到最小下标 i 满足 arr[i] > value，判断条件变为：

if (*mid <= value)
    first = mid + 1;  // 包含等于的情况，继续向右
else
    last = mid;

两者的唯一区别在于对"等于"情况的处理方式，这决定了最终定位的是"左边界"还是"右边界"。

典型应用场景

1. 判断元素是否存在

结合 lower_bound 可高效判断某值是否存在：

bool exists(const vector<int>& v, int target) {
    auto it = lower_bound(v.begin(), v.end(), target);
    return it != v.end() && *it == target;  // 检查是否越界且值匹配
}

2. 统计元素出现次数

利用二者差值可直接计算重复元素个数：

int count(const vector<int>& v, int target) {
    return upper_bound(v.begin(), v.end(), target) -
           lower_bound(v.begin(), v.end(), target);
}

3. 有序插入

保持容器有序性的插入方式：

void insert_sorted(vector<int>& v, int value) {
    auto pos = lower_bound(v.begin(), v.end(), value);
    v.insert(pos, value);  // 插入后仍保持升序
}

4. 自定义比较函数（降序处理）

当序列按降序排列时，需传入 greater()：

vector<int> desc = {7, 5, 4, 4, 2, 1};
auto lb = lower_bound(desc.begin(), desc.end(), 4, greater<int>());
// 此时 lower_bound 表现为查找第一个 ≤ 4 的元素

5. LIS 最长上升子序列

在动态规划求解 LIS 时，常用 lower_bound() 找到替换位置：

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end())
            tails.push_back(num);
        else
            *it = num;
    }
    return tails.size();
}

总结

lower_bound() 与 upper_bound() 是 C++ STL 中极为精巧的设计，通过微小的逻辑差异，分别解决了"下界"与"上界"的定位问题。

cat lower-bound-upper-bound.md|