Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options

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]
[Your Mother]: What a stupid, yet seductive super power. Control of biting insects.
[oiskuu]: Don't you think it's disturbing that the washing machine manual would say not to start it with pets inside?
[oiskuu]: So, how long did it take you to grow up?
[oiskuu]: Have you ever had your temperature taken from the other end?

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (12)
As of 2017-12-18 14:52 GMT
Find Nodes?
    Voting Booth?
    What programming language do you hate the most?

    Results (487 votes). Check out past polls.