rahimuj570's blog

Heres some confusion about upper_bound() in cpp.
By rahimuj570, history, 19 months ago, In English

I don't understand how upper_bound work or give output

here's my code:

#include<bits/stdc++.h>
using namespace std;
int main(){

std::vector<int> v({2,4,1,3});
std::vector<int> v2({2,3,1,4});
auto it=upper_bound(v.begin(), v.end(),2);
auto it2=upper_bound(v2.begin(), v2.end(),2);
cout<<*it<<endl;
cout<<*it2;

return 0;}

I think upper_bound() give me next greater element of the vectors. So as according the value of *it and *it2 will be 4 and 3. But when I run the code, the output is *it=3 and *it2=4.

Output Screenshot link: https://prnt.sc/NqBCnAXtQR8P

I don't understand, what's going wrong. Can anybody clear this thing, please.

  • Vote: I like it
  • -13
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
19 months ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

As i know, upper_bound() (as well as lower_bound()) works on some kind of binary search (you can read about this technique, for example, from this blog; also there is a problem tag in codeforces problemset: "binary search"). This technique requires array to be sorted, so these functions can work "incorrect" (not as can be expected) with shuffled ones. Also you can read about these and related functions here.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It doesn't work like that. upper_bound(v.start(), v.end(), n) will return an iterator pointing to the smallest element $$$x$$$ of the vector such that $$$x > n$$$ or v.end() if no such element $$$x$$$ exists.

Also, the implementation is based on binary search. It will not work in an intended way if the array is not sorted. In your examples the arrays are not sorted which means that the function don't work as intended.

→ Reply