C / C++ / 系统课时

lower_bound 能解决什么问题

lower_bound 能解决什么问题

在有序数据里,很多需求并不是简单判断“有没有”,而是寻找一个精确边界:第一个不小于目标的位置、重复值的起点与终点,或者新元素应该插入在哪里。lower_bound 和 upper_bound 就是为这些场景准备的二分区间算法。

学习目标

  • 理解 lower_bound 与 upper_bound 返回位置的含义
  • 用两个边界定位重复元素形成的半开区间
  • 使用 lower_bound 找到保持序列有序的插入位置

lower_bound 找到的是边界

对于默认的升序比较,std::lower_bound(first, last, value) 返回第一个不小于 value 的元素。如果所有元素都小于目标,它会返回 last。

std::upper_bound 则返回第一个大于 value 的元素。因此,当目标存在重复值时,两者正好围出目标值所在的半开区间 [lower, upper)。

例如序列 1 2 2 2 4 7 查找 2:lower_bound 指向下标 1 的第一个 2,upper_bound 指向下标 4 的 4,所以三个 2 位于区间 [1, 4)。

lower_bound 与 upper_bound 的边界关系

这个定义非常适合边界问题,因为目标不存在时仍然会返回一个有意义的位置,而不是只能告诉你“失败”。

定位重复值和插入点

下面同时演示重复值区间和有序插入。原始序列已经升序,因此可以直接使用默认比较规则。

cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nums{1, 2, 2, 2, 4, 7};

    // 两个边界围出所有值为 2 的元素。
    auto first = std::lower_bound(nums.begin(), nums.end(), 2);
    auto last = std::upper_bound(nums.begin(), nums.end(), 2);

    std::cout << "lower index: " << first - nums.begin() << '\n';
    std::cout << "upper index: " << last - nums.begin() << '\n';
    std::cout << "count: " << last - first << '\n';

    // 3 不存在,但 lower_bound 会给出保持升序的插入位置。
    auto insert_pos = std::lower_bound(nums.begin(), nums.end(), 3);
    std::cout << "insert index: " << insert_pos - nums.begin() << '\n';
    nums.insert(insert_pos, 3);

    for (int value : nums) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

预期输出:

text
lower index: 1
upper index: 4
count: 3
insert index: 4
1 2 2 2 3 4 7

插入 3 时,返回的位置指向原来的 4。在该位置执行 insert 后,前面的元素都小于 3,后面的元素都不小于 3,因此序列仍保持升序。

三种常见需求怎样选择

只判断目标是否存在时,binary_search 的布尔结果最直接。需要第一个可放置位置时使用 lower_bound;需要确定重复值结束位置时使用 upper_bound。如果同时需要重复值的左右边界,还可以使用 std::equal_range 一次得到等价的两个迭代器。

查找某个值 x 是否存在时,也可以先调用 lower_bound,再检查返回迭代器没有到达 end(),并且其元素确实等于 x。这种写法的优势是同一个结果还能继续用于获取位置或执行插入。

有序和比较器仍然是前提

这些边界算法与 binary_search 一样依赖有序区间。默认升序时,“第一个不小于目标”很好理解;使用自定义比较器后,更通用的定义是:lower_bound 返回第一个不再被比较器判定为“位于目标之前”的位置。

例如数据按降序排列时,应在排序和边界查找中都使用 std::greater<int>。不要对降序数据直接套用默认版本,否则返回位置没有可靠意义。

对于 std::vector、std::deque 这类支持随机访问的有序范围,lower_bound 和 upper_bound 都只需要 O(log⁡N)O(\log N) 次比较。它们把“找某个元素”扩展成了“找有序区间的边界”,因此尤其适合区间统计、重复值处理和保持顺序的插入定位。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

lower_bound 能解决什么问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通