C ++中的lower_bound（）

Question

[从网上阅读后，我了解到C ++中的lower_bound()方法用于返回一个迭代器，该迭代器指向[first，last）范围内的第一个元素，该元素的值不少于value。这意味着该函数返回的下一个最小数字的索引正好大于该数字。

因此，对于下面的给定代码，我理解输出为3。但是，由于存在6的重复，我如何使用lower_bound()获得最后6个的索引。我可以为此实现自己的binary_search()，但我想通过lower_bound()知道如何实现。

#include <iostream> 
#include <algorithm>
#include <vector> 

using namespace std; 

int main () 
{ 
    int array[] = {5,6,7,7,6,5,5,6}; 

    vector<int> v(array,array+8); // 5 6 7 7 6 5 5 6 

    sort (v.begin(), v.end()); // 5 5 5 6 6 6 7 7 

    vector<int>::iterator lower,upper; 
    lower = lower_bound (v.begin(), v.end(), 6); 
    upper = upper_bound (v.begin(), v.end(), 6); 

    cout << "lower_bound for 6 at position " << (lower- v.begin()) << '\n'; 
    return 0; 
} 

Answer 1

使用lower_bound和upper_bound对。或一个equal_range-会更好。

Answer 2

您可以在向量中使用反向迭代器，但是为了满足std::lower_bound的排序要求，您需要对比较进行反演，因此需要使用std::greater而不是默认的std::less。但是，这也意味着现在您不是真正在寻找下界，而是在该比较函数的上界，所以：

Answer 3

如果数组已排序，则在lower_bound和upper_bound之间进行迭代，您将获得所有等于枢轴点的元素：

Answer 4

您可以使用lower_bound更新开头和值：