Re: searching a vector array

[zek152]

I am not quite clear if this fulfills the requirements but if all you need to do is to see if a single value is covered you could implement a binary search tree.

The binary search tree could be arranged based on the starting location. Then if the point you are considering is less than or equal to the starting point of a subinterval you go down the left branch. If it is greater than the starting value you check to see if it is less (or equalto) than the ending value. If so then the point is covered. If not then you continue traversing the tree in a recursive manner. if you make it to a null link then the point is not covered.

Hopefully this made sense. The search complexity would be O(log(#subintervals))

interval (1,20]
subintervals (1,3],(5,10],(11,12],(15,17]
A (sort of) balanced tree would look like:
    (5,10]
  (1,3]  (15,17]
       (11,12]

Update: I didn't have time to finish the example. I also made a correction to the traversal algorithm (in italics)

If you consider the number 4 with the above tree
4<=5 so you traverse down the left side.
4>1 && 4>3 so you take the right child
the right child is null so 4 is not covered.
Considering 12.
12>10 so go down right branch
12<=15 so go down left branch
12>11 and 12<=12 so 12 is covered.<

I plan on working out an efficient algorithm for finding and removing subsets of subsets (removing (1,3] when (1,5] is a subset). I will post when complete.

[zek152]

After doing some research I have found the notion of an Interval_tree. This seems like a great data structure for your problem.