CODEWITHSUNDEEP
c++vectorstl
mathnormie
mathnormie

Reputation: 5

upper_bound and find giving different results

I am new to STL and used find() and upper_bound() functions on vector to find the position of 6 . The code is given below 


#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;
}

The output when you run the code is 7 4 ,while I expected it to be 7 7 . What am I doing wrong ?

Upvotes: 0

Views: 119

Answers (1)

TheOperator
TheOperator

Reputation: 6456

cppreference.com for std::upper_bound() explains it nicely (emphasis mine):

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.

In your case, you have a 7 (greater than 6, at index 4) appearing before a 4 (which is equal or less than 6), so the precondition is not met.

The idea of std::upper_bound() and its companions is to quickly do binary searches in sorted arrays. As opposed to linear search as in std::find(), it only needs O(log(n)) time complexity instead of O(n).

Upvotes: 1

Related Questions