in reply to mapping lists

Doh! Sorry to have led so many on a wild goose chase (thanks for all the replies though). But I was so wrapped up in solving the problem of the range limits not being part of the set that I left out a HUGE set of the problem. So, consider that a warmup.

Given the original @F(values are unique, and are probably sorted) return the indices of @F whose values fall within the supplied range.

UPDATE: Although I suppose all that would be required then is to use one of these search techniques (which?) and reverse map the values of @F to the indices. Does this added step give one of the techniques an advatage over the others?

--
I'm not belgian but I play one on TV.

Replies are listed 'Best First'.
Re: UPDATE: mapping lists
by tall_man (Parson) on Jan 25, 2003 at 00:19 UTC
    The values are probably sorted? Oh-oh.

    If you aren't guaranteed they are sorted, you can't use a binary search. You'd have to do a linear pass to test if they are really sorted, and sorting them yourself isn't worth it unless you are going to do lots of range checks on the same data.

    Here is a simple linear method that requires no side data structures. 

    use strict;
my @F = (
      1,
      2,
      4,
      8,
      32..64,
      26
     );

sub range{
  my($lo, $hi) = @_;
  return grep {$F[$_] >= $lo and $F[$_] <= $hi} 0..$#F;
}
print join(',', range(25,35)), "\n";

    [download]
    This is basically what thinker and blokhead did except that my grep is on the indices instead of the values of @F.
[reply]
[d/l]
Re: UPDATE: mapping lists
by Anonymous Monk on Jan 24, 2003 at 23:13 UTC
    I was thinking along the lines of: 
    #!/usr/bin/perl -w

use strict;
use Quantum::Superpositions;

my (@F, @G, @range);

@F = (1, 2, 4, 8, 16, 32..64);

my ($i, $j);
for($i=0; $i<scalar @F; $i++){
  $G[$j++] = $i if (any(@range) == any($F[$i]));
}

print join(',', @G), "\n";

    [download]
[reply]
[d/l]

In Section Seekers of Perl Wisdom