Detect if Integer is within multiple ranges of Integers efficiently

Question

Let's say you have an integer n. And let's say you have a list of non-overlapping integer ranges, for example:

1-9
99-105
160-205
503-600
// many more thousands of ranges, etc ....

I could very easily iterate over all of these and check if n is between each of the bounds and return true, if one is. That would be O(n), which is bad. Can this be done in O(1)?

Some rules:

• The integers themselves are very large and the ranges very wide, so it wouldn't be feasible to just get the complete list of acceptable integers and use something like a Set to do O(1) lookup. Storing that many integers in memory is too expensive. I can only store the list of bounds.
• I'm going to run this test many many times, so I can craft the list into some data structure upfront, if that makes the subsequent lookups more efficient.

I feel that I could get the binary representations of these ranges and build a tree which would yield O(log(n)).

My Real Question

I have a list of IP address subnets. I need to test if a given IP is in any of those subnets. I will have many many IPs to check. I can convert an IP into an integer (1.2.3.4 => 1*2^32 + 2*2^16 + 3*2^8 + 4). And I can convert the subnets similarly. That equates to the "simpler to explain" question above.

Thanks!

Answer 1

Storing ranges in a sorted vector and searching a value by std::lower_bound is O(log(n)).

Which size of integer do you need for IP 200.200.200.200 with that algorithm? Why not just 200200200200?

A four branches tree for IP A.B.C.D for storing the subnets seems more adequate.