Efficient way to store multiple ranges of numbers for future searching

Question

I have a text file full of IP addresses ranges. I use ip2long to convert the addresses to longs so that I have an easy way to check if a given address is within the range. However, I'm looking for an efficient way to store these ranges and then search to see if an IP address exists within any of the ranges.

The current method I'm thinking of is to create an object that has the low end and the high end of a range with a function to check if the value is within range. I would store these objects in a list and check each one. However, I feel this might be a bit inefficient and can get slow as the list increases.

Is there a better way than what I'm thinking?

Answer 1

One of the following data structures may help you:

Segment Tree

From Wikipedia (Implementation):

Is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point.

---

Interval Tree

From Wikipedia (Implementation):

Is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point.

---

Range Tree

From Wikipedia (Implementation):

Is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently.

Answer 2

Assume the ranges do not overlap, otherwise you could combine them into one range.

Then create an array of increasingly ordered begin1, end1, begin2, end2, .... Where begini is inclusive in the range, and endi is just after the range.

Now do a binary search and:

int pos = ... .binarySearch ...
boolean found = pos >= 0;
if (!found) {
    pos = ~pos;
}
boolean atBegin = pos % 2 == 0;
boolean insideRange = (found && atBegin) || (!found && !atBegin);
//Equivalent: boolean insideRange = found == atBegin;

The lookup test is O(log N). The creation of the initial array is much more complex.

Java binarySearch delivers the index when found, and ~index (ones complement, < 0) when not found.

---

Addendum: I think the above can be "smartly" comprised by

boolean insideRange = (Arrays.binarySearch(...) & 1) == 0;

though an explaining comment would definitely be needed. I leave that to the reader.