Alex Rivera | Logout

Range lookup in Java

Asked 2011-11-18T15:25:53.750
10

Suppose, I have an unsorted array of overlapped ranges. Each range is just a pair of integers begin and end. Now I want to find if a given key belongs to at least one of the ranges. Probably, I have to know the ranges it belongs as well.

We can assume the ranges array takes ~1M and fits the memory. I am looking for an easy algorithm, which uses only standard JDK collections without any 3d-party libraries and special data structures, but works reasonably fast.

What would you suggest?

java algorithm search data-structures
Edit
Report

2 Answers

3

I believe this is what you are looking for: http://en.wikipedia.org/wiki/Interval_tree

But check this simpler solution first to see if it fits your needs: Using java map for range searches

answered 2011-11-18T15:32:42.980
1

simple solution with O(n) complexity:

for(Range range: ranges){
  if (key >= range.start && key <= range.end)
    return range;
}

More clever algorithm can be applied if we know more information about ranges. Is they sorted? Is they overlapped? and so on

answered 2011-11-18T15:34:09.277

Your Answer