如何在已排序std::vector中实现查找指定值左右相邻元素的left、right函数

云原生阿岚

2026-10-1

实现方案

前提：容器为升序有序，当前实现支持std::vector、std::set、std::list等所有支持双向迭代器的标准库有序容器。

right 函数实现

你的right函数需求和std::lower_bound的行为完全匹配：std::lower_bound会返回容器中第一个大于等于目标值的元素迭代器，找不到匹配元素则返回end()。

#include <algorithm>

template <typename Container, typename T>
auto right(const Container& c, const T& value) {
    return std::lower_bound(c.begin(), c.end(), value);
}

测试用例验证：

right(v1, 0) → 第一个≥0的元素是0，返回首迭代器 ✅
right(v1, 10000) → 第一个≥10000的元素是48000，返回第二个元素迭代器 ✅
right(v1, 48000) → 第一个≥48000的元素是48000，返回第二个元素迭代器 ✅
right(v1, 60000) → 无符合元素，返回end() ✅

left 函数实现

你的left函数需求是找到小于等于目标值的最大元素，可以通过std::upper_bound配合偏移实现：std::upper_bound返回第一个大于目标值的元素迭代器，将其减1就是最后一个≤目标值的元素，额外处理目标值小于所有元素的边界即可。

#include <algorithm>

template <typename Container, typename T>
auto left(const Container& c, const T& value) {
    auto it = std::upper_bound(c.begin(), c.end(), value);
    // 目标值小于所有元素时返回首迭代器，可根据需求调整为返回c.end()
    if (it == c.begin()) {
        return c.begin();
    }
    return --it;
}

测试用例验证：