从一道LeetCode题出发，实战解析C++ set中lower_bound的正确用法与常见坑点

在算法面试和日常刷题中， set 容器及其边界查询函数 lower_bound 和 upper_bound 的使用频率极高。然而，许多C++学习者在使用这些函数时容易陷入误区，尤其是在处理自定义排序规则或复杂数据结构时。本文将通过一个典型的LeetCode问题，深入剖析这些函数的正确用法和常见陷阱。

1. 问题引入：滑动窗口中的错误案例

假设我们正在解决LeetCode 220题"Contains Duplicate III"，需要在滑动窗口内快速查询满足条件的元素。许多初学者会写出类似这样的代码：

set<int> window;
for (int i = 0; i < nums.size(); ++i) {
    auto it = window.lower_bound(nums[i] - t);
    if (it != window.end() && *it <= nums[i] + t) {
        return true;
    }
    window.insert(nums[i]);
    if (window.size() > k) {
        window.erase(nums[i - k]);
    }
}

这段代码看似合理，但在某些边界情况下会出现错误结果。问题就出在对 lower_bound 返回值的理解上。

2. 理解lower_bound的本质

lower_bound 的核心概念不是简单的"大于等于"，而是 序列中的位置界限 。它的行为会随着容器排序规则的变化而变化：

• 默认升序排列 时：

  • lower_bound(val) 返回第一个 不小于 val的元素位置
  • upper_bound(val) 返回第一个 大于 val的元素位置

• 自定义降序排列 时（如 set<int, greater<int>> ）：

  • lower_bound(val) 返回第一个 不大于 val的元素位置
  • upper_bound(val) 返回第一个 小于 val的元素位置

关键区别 ：

3. 实战修正：正确使用边界查询

回到我们的LeetCode问题，正确的实现应该考虑以下几点：

1. 明确查询范围 ：我们需要找的是 [nums[i]-t, nums[i]+t] 区间内的元素
2. 合理使用边界函数 ： lower_bound 定位区间起点， upper_bound 定位区间终点

修正后的核心代码：

set<long> window;  // 使用long防止整数溢出
for (int i = 0; i < nums.size(); ++i) {
    long num = nums[i];
    auto lb = window.lower_bound(num - t);
    if (lb != window.end() && *lb <= num + t) {
        return true;
    }
    window.insert(num);
    if (window.size() > k) {
        window.erase(nums[i - k]);
    }
}

4. 高级应用：结合equal_range

对于更复杂的查询场景，STL提供了 equal_range 函数，它返回一个包含 lower_bound 和 upper_bound 结果的pair：

auto range = window.equal_range(target);
for (auto it = range.first; it != range.second; ++it) {
    // 处理所有等于target的元素
}

这种方法在 multiset 中特别有用，可以高效地获取所有相等元素的范围。

5. 性能优化与最佳实践

1. 时间复杂度 ：在 set 中， lower_bound 和 upper_bound 都是O(log n)操作
2. 空间优化 ：对于滑动窗口问题，及时移除窗口外的元素
3. 类型安全 ：注意整数溢出问题，必要时使用更大范围的数值类型

推荐实践清单 ：

• 始终明确容器的排序规则
• 在自定义比较器的容器中，先验证边界函数的行为
• 对于范围查询，先写测试用例验证边界条件
• 在性能敏感场景，考虑使用更高效的数据结构如 unordered_set

6. 常见陷阱与调试技巧

在实际编码中，有几个典型错误需要警惕：

1. 错误假设排序顺序 ：忘记容器可能使用自定义排序规则
2. 忽略end()迭代器 ：未检查返回值是否为end()就直接解引用
3. 混淆lower/upper_bound ：在降序容器中使用与升序相同的逻辑
4. 类型不匹配 ：查询值与容器元素类型不一致导致隐式转换问题

调试时可以添加临时打印语句验证理解：

set<int, greater<int>> s = {5, 3, 1};
auto lb = s.lower_bound(4);
cout << "Lower bound of 4 in descending set: " << *lb << endl;  // 输出3

理解 lower_bound 和 upper_bound 的核心在于把握它们作为"界限"的本质角色，而非简单的数值比较。这种理解不仅适用于 set ，也同样适用于 map 、 multiset 等其他有序容器。掌握这些边界查询函数的正确用法，能够显著提升算法实现的质量和效率。