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 ?

Thanks in Advance.

There is a way to do it!

Read under title 'Red black tree' http://codeforces.com/blog/entry/15729

Thank you... :)

http://codeforces.com/blog/entry/11080

http://codeforces.com/blog/entry/10355

Thank you... :)

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 <ext/pb_ds/assoc_container.hpp>

include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

template using ordered_set = tree<T, null_type, less, rb_tree_tag, tree_order_statistics_node_update>;

Hope that it helps;D

how to install these libraries ??? will you please share the appropriate links

bro you could use distance() function

ex : s = {2,5,6,8,10}

to find index of 8 , you just do

That takes linear time; I'm sure the OP wanted something faster.

Also, 5 years ago.

Read this. Be careful, by default, distance() complexity is linear.

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.Performance Comparison

5 years ago, man

yes , but it will be useful for someone someday ,

lol, 5 years ago, indeed.

Thanks for the hint.