math - Algorithm to query between which boundaries a number is in -


i trying query interval in set of non-overlapping intervals number in. realise there numerous solutions problem out there already, believe case yet again special , different.

i dynamically adding , removing boundaries segregate interval negative positive infinity sections. there no holes in these sections, i.e. set of boundaries/intervals continuous. means when boundary removed, sections below , above merged.

the boundaries added in no particular order. see following image clarification:

enter image description here

in case queried number on boundary, don't care of regions belongs to, , want return either 1 of them.

the number of queries may considerably larger or considerably smaller number of boundaries.

a naive algorithm run in o(n). assuming until next query made, set of boundaries have changed completely, faster using binary search trees, think (?), not seem optimal solution.

is there algorithm fits scenario?


Comments

Popular posts from this blog

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

python Tkinter Capturing keyboard events save as one single string -

sql server - Why does Linq-to-SQL add unnecessary COUNT()? -