在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++上的二進制搜索與比較

回答

相關問題