How to find if a point is within a set of intervals?

Question

I am looking for the fastest way to decide whether or not a point on a line is within a subset of this line. I am given an integer Point, and I also have a "list" of either:

1. Points, represented by an integer ( 3, 10, 1000, etc)
2. Intervals, that I represent by 2 integers ( 2:10 is all integers from 2 to 10 inluded, 50:60, etc)

In this example, if the value of my point is 5, then I return true because it is included in an interval, same for 55. If my point is equal to 1000, I also return true because it matches the list of points.

I am looking for a fast way (quicker than linear) to check for this condition, WITHOUT having to instanciate as many integer as there are possible points (ie, for a 1:1000 interval I don't want to instanciate 1000 integers). Can this be done in a logarithmic time?

Thanks

edit : you can consider that any time taken to pre-process the list of data is equal to 0, because once my initial intervals are processed I need to apply this test to 10k points

Answer 1

Hm, maybe you can use an interval or a segment tree:

• http://en.wikipedia.org/wiki/Segment_tree
• http://en.wikipedia.org/wiki/Interval_tree

Answer 2

If you have the integers ranges sorted and the ranges are non-overlapping, you can perform binary search to find the correct range in logarithmic time.

Are there any constraint on the range? Based on that you can probably come up with hashing function to search in constant time. But this depends on how your constraints are.

Answer 3

After reflexion, I think that the following code should work in logarithmic time, excluding the time needed to build the map:

enum pointType {
    point,
    open,
    close
};
std::map<long int, pointType> mapPoints;

mapPoints.insert(std::pair<long int, pointType>(3, point));

//create the 5:10 interval:
mapPoints.insert(std::pair<long int, pointType>(5, open));
mapPoints.insert(std::pair<long int, pointType>(10, close));

int number = 4;
bool inside = false;
std::map<long int, pointType>::iterator it1 = mapPoints.lower_bound(number);

if(it1->first == number || it1->second == close) {
    inside = true;
}

I think this should work as long as the map is filled properly with non-overlapping intervals