Aly's blog

HOW Can i binary search on a set?????
By Aly, history, 3 years ago, In English

set iterator is not like vector iterator i cant add to the iteratire so how can i do binary search on a set and how can i find the diffrence betwen two positions in a set

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

You can use : s.lower_bound(x) s.upper_bound(x)

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

You can solve pbds if you are facing problem due to limitations in set and multiset. You can learn it from here: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/amp/

Make sure you are using c++20, because pbds use red-black tree and it applies operations in log(n) but it consumes slidely more time than set and multiset.C++20 is faster. So it should be preferred. You can see the blog to realise that: https://mirror.codeforces.com/blog/entry/113537

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

use ordered_set with s.order_of_key(x) which gives the position of x in log(n) time.

→ Reply