c++中如何使用std::lower_bound实现二分查找_c++查找元素位置【汇总】_技术教程

std::lower_bound查找第一个不小于目标值的位置，返回迭代器而非下标，需作用于已排序容器，时间复杂度O(log n)，使用前必须检查it != end()以防越界解引用。

std::lower_bound 查找的是“第一个不小于目标值”的位置

它不判断元素是否存在，只返回插入位置——如果目标值存在，返回其首次出现的迭代器；如果不存在，返回它应该插入的位置（保持有序）。返回类型是 Iterator，不是 int 下标，需用 std::distance 或减法转为索引。

必须作用于**已排序**的容器（如 std::vector、std::array），否则行为未定义
底层是 O(log n) 二分，但比手写循环更安全、更泛型
对 std::vector 可直接用 vec.begin() 和 vec.end()；对原生数组要用 std::begin(arr) / std::end(arr) 或指针

正确获取下标：用迭代器减法，别用 std::distance 搞错范围

对随机访问迭代器（vector、array、原生数组），直接用 it - container.begin() 最高效；std::distance 虽通用，但对非随机访问容器（如 std::list）是 O(n)，且容易传错范围（比如误传 container.end() 作起点）。

std::vector v = {1, 2, 2, 4, 5};
auto it = std::lower_bound(v.begin(), v.end(), 2);
int pos = it - v.begin(); // ✅ 正确：pos == 1
if (it != v.end() && *it == 2) {
    // 元素存在，且 pos 是第一次出现的位置
}

常见错误：忘记检查迭代器是否越界就解引用

std::lower_bound 返回 container.end() 表示所有元素都小于目标值。此时若直接 *it 会触发未定义行为，尤其在查找最大值或目标超出范围时极易出错。

必须先判断 it != container.end()
若还需确认“元素确实等于目标”，得额外比较 *it == value
不要把 lower_bound 当成“查找成功与否”的判据——它永远返回一个合法迭代器（哪怕指向 end）

和 upper_bound、equal_range 的关键区别在哪

std::lower_bound 定位左边界，std::upper_bound 定位右边界（第一个大于目标值的位置），两者差值就是重复元素个数。std::equal_range 一次性返回 pair，适合需要完整区间场景，但多一次二分开销。

std::vector v = {2, 2, 2, 4, 4};
auto [l, r] = std::equal_range(v.begin(), v.end(), 2); // C++20 结构化绑定
// l == v.begin(), r == v.begin() + 3 → count = r - l == 3
// 等价于：l = lower_bound(..., 2); r = upper_bound(..., 2);