Jahid's blog

By Jahid, 5 years ago,

I am trying to find the position of an element in set using lower bound or binary search i.e, in lg(n) time.

For example, Elements in set are: 1 2 4 5 7.

I need to find the position of 4 which is in 3rd position. I have tried but can't do this. Is there any way ?

• +5

 » 5 years ago, # |   +3 There is a way to do it! Read under title 'Red black tree' http://codeforces.com/blog/entry/15729
•  » » 5 years ago, # ^ |   0 Thank you... :)
 » 5 years ago, # |   +37
•  » » 5 years ago, # ^ |   0 Thank you... :)
 » 5 years ago, # |   0 You can simply use ordered set instead of "simple" set. That's how it works: ordered_set s; cout << s.order_of_key(3) << endl; — the number of elements in s less than 3 (in this case, 0-based index of element 3)cout << *s.find_by_order(1) << endl; — 1-st elemt in s (in sorted order, 0-based)P.S. here is some usefull stuff you need to deal with working with ordered set:include include using namespace __gnu_pbds;template using ordered_set = tree;Hope that it helps;D
•  » » 3 months ago, # ^ |   0 how to install these libraries ??? will you please share the appropriate links
 » 10 days ago, # |   -29 bro you could use distance() functionex : s = {2,5,6,8,10}to find index of 8 , you just do distance(s.begin(),s.find(8)); this will return no of elements between two iterators i.e 3
•  » » 10 days ago, # ^ |   +11 That takes linear time; I'm sure the OP wanted something faster.Also, 5 years ago.
•  » » 10 days ago, # ^ |   0 Read this. Be careful, by default, distance() complexity is linear.
•  » » 10 days ago, # ^ | ← Rev. 3 →   0 The time-complexity of the std:distance is $O(N)$ when its parameters type does not meet the requirements for Legacy Random Access Iterator. On the other hand, the time-complexity of the order_by_key member function of G++ Order-Statistics Sets is $O(\log~N)$. Therefore, the latter function is much faster when the number of items in the set is large. You may check the following test results.
•  » » » 10 days ago, # ^ |   +3 5 years ago, man
•  » » » » 10 days ago, # ^ |   +1 yes , but it will be useful for someone someday ,
•  » » » » 10 days ago, # ^ |   0 lol, 5 years ago, indeed.Thanks for the hint.