Take the 2-minute tour ×

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?


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

share|improve this question
can the intervals overlap? I don't know for sure if that matters, but it feels like it should. –  Almo Apr 12 '12 at 19:52
they could, but I can pre-process my data so that they don't anymore, which is no a problem time-wise because I'm using the same interval sets to then process 10k points –  lezebulon Apr 12 '12 at 19:54
Are they ordered? –  Freddy Apr 12 '12 at 19:55
->check the edit –  lezebulon Apr 12 '12 at 20:01
Do you need to know which intervals a point is in, or merely whether it is in any of them or not? –  Karl Bielefeldt Apr 12 '12 at 20:29
show 3 more comments

6 Answers

up vote 5 down vote accepted

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

share|improve this answer
+1 for the correct answer. This is a well-studied computational geometry problem ("1D stabbing query"). –  Nemo Apr 12 '12 at 23:45
add comment

First check a hash_map of points. That's the simple check.

Then simply order a map of intervals by the first coordinate and then find lower_bound of the point.

Then check if you are contained in the element returned. If you aren't in that, you aren't in any.

share|improve this answer
There seem to be assumptions in some of the responses that the intervals might overlap. You are in control of the data structure you use to solve this issue - it has no dependency necessary on outside or the initial interval set. So you should not be storing overlapping intervals in general - join them when inserting into the map. Whenever dealing with intervals this is fairly standard. –  ex0du5 Apr 12 '12 at 20:02
add comment

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.

share|improve this answer
I think I can assume that the range is between 0 and 10 millions. –  lezebulon Apr 12 '12 at 19:59
If some ranges overlap you can sort them and collapse the overlapping ones into a single range. –  Mark Ransom Apr 12 '12 at 20:26
add comment

You could do that in sublinear time GIVEN a tree data structure (I'd recommend a B-tree),if you don't count the time taken to build the tree (most trees take n log n or similar time to build).

If you just have a plain list, then you cannot do better than linear because in the worst case you potentially have to check all points and intervals.

share|improve this answer
add comment

You can use a Bloom Filter to test a point and see if it's not in an interval, in linear O(1) time. If it passes that test you must use another method such as a binary search to see if it's definitely part of an interval, in O(log n) time.

share|improve this answer
Is the idea to hash each point in the interval? –  Matthias Vallentin Apr 12 '12 at 20:13
@MatthiasVallentin, yes it is. The size of the Bloom Filter depends on the number of points set and the probability of false positives, not on the possible range of inputs. –  Mark Ransom Apr 12 '12 at 20:24
Thanks, I understand your idea now. However, there are many choices which Bloom filter parameters to fix initially. Since this data structure is often used in space-constrained environments, a common approach is to assume a fixed size and set cardinality to derive the optimal value of k, the number of hash functions. Could you clarify what you mean by "size"? Once instantiated, the size of the (basic) Bloom filter typically does not change anymore. –  Matthias Vallentin Apr 12 '12 at 21:30
@MatthiasVallentin, sorry I was unclear. What I meant to say is that once the number of points and the probability of false positives (and the number of hash functions) has been selected, the size of the filter arrays can be calculated. The point being it is not dependent on the range of inputs. –  Mark Ransom Apr 12 '12 at 21:42
add comment

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

enum pointType {
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

share|improve this answer
add comment

Your Answer


