How to find a range from a set of adjacent ranges for a given number

Question

so simple to put, here is what I am trying to do:

I have a set of Range objects that are adjacent (do not overlap, without spaces between them), each of which contains start and end int, as well as a link to another obj object. These ranges do not have a fixed size (the first can be 1-49, the second 50-221, etc.). This collection can grow quite large.

I hope to find a way to search for a range (or, more specifically, the object that it refers to) that includes the given number, without having to iterate over the entire collection, checking each range to see if it includes that number. These searches will be performed frequently, so speed / performance is key.

Does anyone know of an algorithm / equation that could help me here? I am writing in Java. I can provide more detailed information if necessary, but I decided that I would try to make it simple.

Thanks.

Answer 1

If it seems to you that you want to use TreeMap , where the key is at the bottom of the range and the value is Range .

Then, to determine the correct range, simply use the floorEntry() method to very quickly get the closest (smaller or equal) Range that the key should contain, for example:

  TreeMap<Integer, Range> map = new TreeMap<>(); map.put(1, new Range(1, 10)); map.put(11, new Range(11, 30)); map.put(31, new Range(31, 100)); // int key = 0; // null // int key = 1; // Range [start=1, end=10] // int key = 11; // Range [start=11, end=30] // int key = 21; // Range [start=11, end=30] // int key = 31; // Range [start=31, end=100] // int key = 41; // Range [start=31, end=100] int key = 101; // Range [start=31, end=100] // etc. Range r = null; Map.Entry<Integer, Range> m = map.floorEntry(key); if (m != null) { r = m.getValue(); } System.out.println(r); 

Since the tree is always sorted in the natural order of the lower range border, all your searches will in the worst case be O (log (n)).

You need to add a health check when your key is completely out of bounds (for example, when the key is outside the map, it returns the last Range on the map), but this should give you an idea of ​​how to proceed.

Answer 2

Assuming your search queries are of utmost importance and you can save O (N) memory and approximately O (N ^ 2) preprocessing time, the algorithm would be:

• enter the ObjectsInRange class that contains: the start of the range ( int startOfRange ) and the set of objects ( Set<Object> objects )
• enter ArrayList<ObjectsInRange> oir , which will contain ObjectsInRange , sorted by startOfRange
• for each Range r , make sure that there are ObjectsInRange (let's call them a and b ) such that a.startOfRange = r.start and b.startOfRange = b.end . Then for all ObjectsInRange x between a and before (but not including) b add r.obj to their x.objects set

Thus, the search is as follows:

• for an integer x , find i that oir[i].startOfRange <= x and oir[i+1].startOfRange > x
• note: i can be found dividing in half at O ​​(log N) time!
• your oir[i].objects

Answer 3

If the collection is ordered, you can implement a binary search to find the correct range in O (log (n)) time. This is not as effective as hashing for very large collections, but if you have less than 1000 or so, it can be faster (because it is easier).