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.
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.