| Subject: | possible bug in Search::Binary |
| Date: | Tue, 01 Dec 2009 12:15:11 -0500 |
| To: | bug-Search-Binary [...] rt.cpan.org |
| From: | Brad Friedman <friedm [...] mcb.harvard.edu> |
Although the documentation says that search is guaranteed to be
restricted to the range $min to $max inclusive, it is actually possible
to go one-past-the-end, if the search key compares larger than the
entire search set. This could potentially lead to undesirable
auto-vivification. Maybe users should be made aware to write the reader
function in a way that protects against this, or perhaps Search::Binary
should be changed to prevent reading at position $max + 1.
Note that this is not a problem when searching an array of scalars,
since although $x[$pos]{key} will autovivify $x[$pos] to refer to an
empty hash, $x[$pos] alone will not autovivify $x[$pos].
Example:
#!/usr/bin/perl
use strict;
use Search::Binary;
my @x = ({a => 1}, {a => 4}, {a => 5}, {a => 9}, {a => 12});
my $last_pos;
sub reader {
my (undef, $val, $pos) = @_;
$pos = $last_pos + 1 unless defined $pos;
$last_pos = $pos;
return ($val <=> $x[$pos]{a}, $pos);
}
foreach my $x (15, 15) {
my $next_pos = binary_search(0, $#x, $x, \&reader, undef);
print "Next_pos of $x is $next_pos\n";
}
Output is
Next_pos of 15 is 5
Next_pos of 15 is 6
But ought to be
Next_pos of 15 is 5
Next_pos of 15 is 5
Users can fix it by protecting non-existent array elements...
sub reader {
my (undef, $val, $pos) = @_;
$pos = $last_pos + 1 unless defined $pos;
$last_pos = $pos;
#### Next two lines different ####
my $a = exists $x[$pos] ? $x[$pos]{a} : undef;
return ($val <=> $a, $pos);
}
Or Search::Binary could be changed.