binary-search - 下界与二分搜索

Question

我正在学习一些 STL功能，我遇到了这个功能
lower_bound .我很困惑，为什么人们不使用 下界而不是 二分查找因为两者都做同样的事情，所以它们都有 O(log n) 复杂度。

只用lower_bound 编写一行代码是不是比用二进制搜索编写8-9 行if-else 语句更好，还是它们对lower_bound 的任何限制我不知道，因为人们不经常使用它?

Answer 1

binary_search (IMO) 的名字很糟糕。它通过二分搜索告诉你一个项目是否存在于你的集合中。它没有告诉你在哪里。
lower_bound告诉您该项目应该在集合中的哪个位置，但实际上并不验证该项目是否存在于集合中的那个位置。您需要检查自己(并注意不要取消引用 end 迭代器!)。

equal_range 告诉您该项目应该去哪里，以及(基于 first 和 second 之间的距离)该范围内实际存在多少项目，如果该项目不存在，则为零。在我看来这是最有用的。比 lower_bound 稍慢但不是很多。