c++ - 如何以最有效的方式在已排序的 C++ vector 中查找值？

Question

我看过 find和 binary_search ，但 find 没有利用 vector 已排序这一事实，并且 binary_search 只返回真或假，而不是它找到值的位置。有什么功能可以让我两全其美？

Answer 1

您可以使用 find 在 O(N) 时间内定位任何容器中的特定元素。使用 vector ，您可以进行随机访问并利用 std 算法的 lower_bound (log2(N))、upper_bound 或 equal_range 类。 std::lower_bound会为你做的。它位于 binary_search 顶部的等效行为部分。但是，binary_search 的用处仅限于yes 和no 答案(可能在未来的C++ 版本中命名需要改进；binary_in())。