habib_rahman's blog

How do I do a binary search in a multiset or in a priority queue?
By habib_rahman, history, 10 years ago, In English

I want to do binary search on a multiset, because I need to know "How many elements in the multiset greater or equal to x". And obviously I want to get the data in O(logn).

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Multisets support only lower bound and upper bound operations, and not operations of the type number of elements  ≥ X. For this purpose, you can use a BIT, or if the values are too large, then compression with a BIT.

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

STL pb tree

→ Reply