Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

Re: searching a vector array

by Grimy (Pilgrim)
on Jun 09, 2011 at 17:17 UTC ( #908961=note: print w/replies, xml ) Need Help??

in reply to searching a vector array

If there's many more numbers than intervals, iterating over the number is indeed a bad idea. But if I understand your demand correctly, the desired can be achieved by iterating over intervals (or rather, over their min and max values: 2..5 and 4..7 is the same as 2..7 and 4..5 regarding coverage).

So you would have to create two arrays (e.g. @min and @max) holding respectively the lower and higher bounds of all intervals. Then:

my $count = 0; foreach $min (@min) { $count++ if ($_[0] >= $min) } foreach $max (@max) { $count-- if ($_[0] > $max) } return $count;
Would give the coverage of $_[0]. Of course, it can be optimized further by sorting @min and @max beforehand and using dichotomy, which would get you an O(ln(X)).

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://908961]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (7)
As of 2017-08-20 08:14 GMT
Find Nodes?
    Voting Booth?
    Who is your favorite scientist and why?

    Results (313 votes). Check out past polls.