c++ - C++ 中的 lower_bound()

Question

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

因此，对于下面给定的代码，我知道输出是 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——这样会更优化。

upper_bound 和 equal_range 的高位部分都将超过最后一个“6”。与end相同，不是最后一个，而是过去最后一个。