Dabagh's blog

Question about search in sets (C++)
By Dabagh, 8 years ago, In English

Hi.

Consider a set of integers S and an integer X.

How to find the maximum integer less than X in S using lower_bound and/or upper_bound?!

How to find the minimum integer greater than X in S using lower_bound and/or upper_bound?! Example :

S = {2 , 3 , 4 , 7 , 8 , 9} , X = 5

maximum integer less than 5 = 4

minimum integer grater than 5 = 7.

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

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

1)

auto it = s.lower_bound(x);
if (it != s.begin()) ans = *(-- it);

2)

auto it = s.upper_bound(x);
if (it != s.end()) ans = *it;
→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Good day to you!

Here are a few usages, too see, how to get elements around :)

i.e:

upper_bound finds first higher

lower_bound finds first higher/equal

You can use "--/++" to move around

PS: Beware of begin/end (not to "get" these elements) .. one can check by "==S.end()" / "S.begin()" :)

Hope I have not made any mistake ^_^

Good Luck!

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Just to note: it is OK to dereference begin(), but you shouldn't do it with end(). Also avoid doing --begin().

    → Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Thanks haposiwe and -Morass- .

I didn't know --it works!

→ Reply