Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic

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)).

Comment on Re: searching a vector array
Download Code

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://908961]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (10)
As of 2015-10-06 15:54 GMT
Find Nodes?
    Voting Booth?

    Does Humor Belong in Programming?

    Results (154 votes), past polls