rahimuj570's blog

By rahimuj570, history, 12 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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You need to sort v first and then only you can use upper bound

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

your vector should be sorted... upper bound and lower bound only can apply if vector is sorted.

»
12 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.

»
12 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.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks Everyone ... I got it...