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

$\endgroup$
  • 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 Nov 12 '14 at 5:36
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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