在C++上的二进制搜索与比较

我想在一个排序的向量V上执行二进制搜索C++。特别是，我没有兴趣找到矢量的入口的确切值。我想找到满足V [j-1] < = X < V [j]的条目的位置j，其中X是输入值。在C++上的二进制搜索与比较

例如：对于矢量v = {1,4，7，12，17，55}并且X = 8，则该函数将返回3.

可否使用STD功能binary_search，与O（log（2））的复杂性？

又如何？

非常感谢，

铝。

来源

2013-06-11 altroware

不应该返回7吗？ – 2013-06-11 16:02:57

binary_search只是查看条目是否存在的函数，它不返回索引。 @Armin他希望返回包含大于X的第一个值的索引。 – Egari

@Egari然后它应该是3。 – 2013-06-11 16:07:56

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

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

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

来源

2013-06-11 16:33:34 akshat

感谢您的答案！ – altroware

这个标准函数是upper_bound和lower_bound。阅读这些

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

如果向下滚动这些页面一点，你会发现例子应该把事情说清楚:)

来源

2013-06-11 16:04:32

了一份关于巴尔托什链接的功能：

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。这是因为可以插入x的半开区间[first,last)为空。

请注意，这通常是低于实际要求更加有用，因为

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

插入之前给定的迭代器，让您可以随时使用的upper_bound结果在这里。

来源

2013-06-11 16:32:54 Useless

在C++上的二进制搜索与比较

回答

相关问题