1
$\begingroup$

I have a large number (millions) of IP ranges which might overlap. An IP range should contain the start IP, stop IP and an range id. How can I efficiently find which ranges contain a given IP?

I could iterate over all the ranges and check for every range if it contains the IP, but I'm looking for a complexity better than O(n).

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Convert your IP address into an integer: etc: 192.168.0.1 -> 192168000001. Then use an interval tree to find all ranges that intersect with a given number. $\endgroup$
    – 1110101001
    Commented Nov 12, 2014 at 5:36

1 Answer 1

Reset to default
3
$\begingroup$

Store your IP address as an integer or long depending on whether it is 32 or 64 bit. Then put the ranges into an interval tree or similar data structure that will allow you to find all ranges that intersect with a given range or point (in this case the IP address you want to check against). This will have a query time of O(lg N) after a preprocessing time of O(N lgN). For K queries this is thus O((N+K)*lg N) which should be fast enough.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.