Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Aly's blog

HOW Can i binary search on a set?????
By Aly, history, 11 months 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

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

Auto comment: topic has been updated by Aly (previous revision, new revision, compare).

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

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

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks , but i want to find the index of the returned iterator from the function

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

      It's impossible ! :(

      But you can use Ordered_Set

      ref: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/

      → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Sounds like you need a self-balancing binary search tree. You can learn something about __gnu_pbds :: tree, which has implemented one.

      → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      index can be find using distance of required iterator with the begin iterator, distance is present in c++ stl.

      → Reply
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        That is O(n) if you use a set (or multiset, for that matter), since iterators work differently in those data structures. The reason it works in O(1) for a vector is that vectors have random-access iterators.

        → Reply
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks :)

        → Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

lower_bound(k) //O(n)

s.lower_bound(k) //O(log n)

→ Reply
»
11 months ago, # |
← 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://codeforces.com/blog/entry/113537

→ Reply
»
11 months ago, # |
  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