c++ - std::lower_bound 和 std::upper_bound 的基本原理？

Question

STL 提供二分查找函数 std::lower_bound 和 std::upper_bound，但我倾向于不使用它们，因为我无法记住它们的作用，因为他们的契约(Contract)对我来说似乎完全是个谜。

只看名字，我猜“lower_bound”可能是“last lower bound”的缩写，
即排序列表中的最后一个元素 <= 给定的 val(如果有)。
同样，我猜“upper_bound”可能是“第一个上限”的缩写，
即排序列表中 >= 给定 val(如果有)的第一个元素。

但是文档说他们做的事情与此完全不同——对我来说，这似乎是一种倒退和随机的混合。套用文档:
- lower_bound 找到 >= val
的第一个元素 - upper_bound 找到 > val

的第一个元素

所以 lower_bound 根本找不到下限；它找到第一个 upper 边界!？而upper_bound 会找到第一个严格上限。

这有意义吗？？你怎么记得的？

Answer 1

如果您在范围 [first, last) 中有多个元素的值等于您要搜索的值 val，那么范围 [l, u) 其中

l = std::lower_bound(first, last, val)
u = std::upper_bound(first, last, val)

恰好是在 [first, last) 范围内等于 val 的元素范围。所以 l 和 u 是 相等范围 的“下限”和“上限”。如果您习惯于以半开区间的方式思考，那是有道理的。

(请注意，std::equal_range 将在一次调用中返回一对中的下限和上限。)