c++ - 带有比较的c ++上的二进制搜索

Question

我想在排序后的向量 V 上对 c++ 执行二进制搜索。特别是，我对找到向量条目的确切值不感兴趣。我想找到满足 V[j-1] <= X < V[j] 的条目的位置 j，其中 X 是输入值。

例如：对于向量 v={1, 4, 7, 12, 17, 55} 和 X=8，函数应该返回 3。

我可以使用复杂度为 O(log(2)) 的 STD 函数 binary_search 吗？

如何？

非常感谢，

铝。

Answer 1

为此的标准函数是upper_bound 和lower_bound。阅读这些

http://www.cplusplus.com/reference/algorithm/upper_bound/ http://www.cplusplus.com/reference/algorithm/lower_bound/

如果您稍微向下滚动这些页面，您会发现应该让事情变得清晰的示例：）

Answer 2

关于 Bartosz 链接的函数的注释：

• upper_bound(begin, end, value)返回大于给定值的第一个元素。这是可以插入并保留排序的间隔的结尾（或过去的结尾）
• lower_bound(begin, end, value)返回不小于给定值的第一个元素。这是可以插入的区间的开始

所以在实践中：

std::vector<int> v = {1, 4, 7, 12, 17, 55};
int x = 8;
auto first = std::lower_bound(v.begin(), v.end(), x);
auto last = std::upper_bound(first, v.end(), x);

应该给first == last && *first == 12。[first,last)这是因为x可以插入的半开区间是空的。

请注意，这通常比您实际要求的更有用，因为

std::vector::insert(iterator, value)

在给定迭代器之前插入，因此您始终可以使用upper_bound此处的结果。

Answer 3

根据您的要求，要使用的正确 STL 函数是 upper_bound。句法：

upper_bound(V.begin(),V.end(),val)-V.begin()

将返回您寻找的基于 0 的索引。