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.


In reply to Re: searching a vector array by zek152
in thread searching a vector array by baxy77bax

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.