Value lookup map for values between limits with overlap

I am trying to speed up my algorithm with a map. Basically I'm searching for a reference because I don't know how to google my problem.

I have specific objects for a range of values. Now I need to find the object that is used for this value. Example:

 x --->

|0 ---- object A ---- 100|                  |140 -- object D -- 200|
                 |80 -- object B -- 120|
         |50-object C-100|

So if I want to do something with x = 10 I want to get object A. If I have x = 90 I want to get object A, object B and object C.

At the moment I am running a loop through all the objects and checking their limits. But there is an order (obviously) in the x. I am pretty sure (or at least hoping) to use this order to make my implementation faster. Something like a lookup map with overlapping limits.

The request for a x value is done in a numeric implementation. It is called very often (between 10'000 and 10'000'000 times depending on precision, grid size of my problem, size of the real problem, ...).

PS: When I'm trying to google I only find something about google maps or normal lookup tables. If you have something I can google, I'm also happy with this.

Solution

You are searching for an interval tree. They area specialized type of binary trees, and much more efficient than a traditional linear lookup, which would require O(N) lookup time. Interval trees need only:

Queries require O(log n + m) time, with n being the total number of intervals and m being the number of reported results. Construction requires O(n log n) time, and storage requires O(n) space.

Since it is described in a standard textbook on algorithms (Cormen, Leiserson, Rivest & Stein's's "An introduction to algorithms"), you will find plenty of examples online written in different languages, with the CLRS version used as a reference implementation.