I am trying to query what interval in a set of non-overlapping intervals a number is in. I realise that there are numerous solutions to this problem out there already, but I believe that my case is yet again special and somewhat different.
I am dynamically adding and removing boundaries that segregate the interval from negative to positive infinity into sections. There are no holes in these sections, i.e. the set of boundaries/intervals is continuous. This means that when a boundary is removed, the sections below and above it are merged.
The boundaries are added in no particular order. See the following image for clarification:
In case the queried number is exactly on a boundary, I don’t care which of the regions it belongs to, and want to return either one of them.
The number of queries may be considerably larger or considerably smaller than the number of boundaries.
A naive algorithm would run in O(n). Assuming that until the next query is made, the set of boundaries will have changed completely, this could be faster than using binary search trees, I think (?), but this does not seem like an optimal solution.
Is there some algorithm that fits this scenario?