c++ - upper_bound 并找到不同的结果

Question

我是 STL 的新手，在 vector 上使用了 find() 和 upper_bound() 函数来找到 6 的位置。代码如下

#include <bits/stdc++.h>

using namespace std;

int main()
{
    vector<int> sam ={1,2,5,3,7,8,4,6};
    int f=upper_bound(sam.begin(), sam.end(), 6)- sam.begin();

    vector<int>::iterator it; 
    it =find (sam.begin(), sam.end(), 6);
    int d=it - sam.begin() ;
    cout<<d<<" "<<f<<endl;

    return 0;
}

运行代码时的输出是 7 4 ，而我预计它是 7 7 。 我做错了什么？

Answer 1

cppreference.com for std::upper_bound() 解释得很好(强调我的):

Returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found.

The range [first, last) must be partitioned with respect to the expression !(value < element) or !comp(value, element), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.

在您的例子中，您有一个 7(大于 6，在索引 4 处)出现在 4(等于或小于 6)之前，因此不满足先决条件。 p>

std::upper_bound()的想法它的同伴是在排序数组中快速进行二进制搜索。与 std::find() 中的线性搜索相反，它只需要 O(log(n)) 的时间复杂度而不是 O(n)。