C++ lower_bound 为什么找不到区间中已有的元素？

2026-11-04数据小许

第二段代码没有满足 std::lower_bound 对查找区间的分区要求，因此无法保证得到有效结果。这不能说明标准库存在 bug。

lower_bound 对输入有什么要求？

lower_bound 使用二分查找，不会逐个检查元素。对于这里的默认比较，查找区间必须按 element < 4 的结果分区：小于 4 的元素都在前面，不小于 4 的元素都在后面。

满足这个条件时，它返回第一个不小于 4 的元素；如果没有这样的元素，就返回传入区间的终点。

升序排列的区间满足这一要求。严格来说，算法只要求区间针对本次查找值正确分区，不要求整个容器都有序。

为什么第一段成功，第二段失败？

两次调用都从 udata.begin() + 1 开始，因此首元素 5 不参与查找。

第一段实际查找的区间只有：

[4]

它满足分区要求，lower_bound 会返回指向 4 的迭代器。

第二段实际查找的区间是：

[4, 1, 2]

各元素与目标值的比较结果为：

元素：        4      1     2
元素 < 4：  false  true  true

不小于 4 的元素出现在小于 4 的元素之前，违反了分区要求。此时调用的行为未定义，不能依赖它返回什么，也不能保证断言通过。

常见的二分实现可能先检查中间元素 1，因为 1 < 4 而排除左半部分，连同其中的 4 一起跳过，最终返回 end()。这可以解释观察到的现象，但不能保证该输入下一定会得到这个结果。

需要二分查找时，先排序查找区间

如果允许调整元素顺序，可以先对实际查找区间排序：

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <vector>

int main() {
    std::vector<std::size_t> udata = {5, 4, 1, 2};

    std::sort(udata.begin() + 1, udata.end());
    // 整个容器变为 {5, 1, 2, 4}。
    // 实际查找区间为 {1, 2, 4}。

    auto it = std::lower_bound(udata.begin() + 1, udata.end(), 4);
    assert(it != udata.end());
    assert(*it == 4);
}

如果要确认目标值确实存在，需要先判断迭代器不是 end()，再检查 *it == 4。lower_bound 也可能返回大于目标值的元素。

需要保留原顺序时，使用 find_if

如果要在未排序区间中按原顺序查找第一个大于或等于 4 的元素，可以使用线性查找：

std::vector<std::size_t> udata = {5, 4, 1, 2};

auto it = std::find_if(
    udata.begin() + 1,
    udata.end(),
    [](std::size_t value) { return value >= 4; }
);

assert(it != udata.end());
assert(*it == 4);

find_if 不要求区间有序，最坏情况下需要检查整个区间。如果只想查找恰好等于 4 的元素，可以使用 std::find。