CUFP
GrandFather
snippet
<div class="Description"><p>In [id://503154] I posted a binary search snippet. Having recently revisited the code I've rolled in the [id://503309|cmp suggestion] [zby] made, handle empty lists and generally pimped the code.</p>
<p>This is the updated code. Note that <c>undef</c> is returned for an empty list.</p>
<readmore title="Test and sample usage code">
<c>
use strict;
use warnings;
my @array = (1, 3, 5, 8, 10);
print "\n", join ", ", @array, "\n";
print "Found 0 at " . BinSearch (0, \&cmpFunc, \@array) . "\n";
print "Found 1 at " . BinSearch (1, \&cmpFunc, \@array) . "\n";
print "Found 2 at " . BinSearch (2, \&cmpFunc, \@array) . "\n";
print "Found 5 at " . BinSearch (5, \&cmpFunc, \@array) . "\n";
print "Found 8 at " . BinSearch (8, \&cmpFunc, \@array) . "\n";
print "Found 10 at " . BinSearch (10, \&cmpFunc, \@array) . "\n";
print "Found 11 at " . BinSearch (11, \&cmpFunc, \@array) . "\n";
@array = (1, 3, 5, 8,);
print "\n", join ", ", @array, "\n";
print "Found 0 at " . BinSearch (0, \&cmpFunc, \@array) . "\n";
print "Found 1 at " . BinSearch (1, \&cmpFunc, \@array) . "\n";
print "Found 2 at " . BinSearch (2, \&cmpFunc, \@array) . "\n";
print "Found 5 at " . BinSearch (5, \&cmpFunc, \@array) . "\n";
print "Found 8 at " . BinSearch (8, \&cmpFunc, \@array) . "\n";
print "Found 9 at " . BinSearch (9, \&cmpFunc, \@array) . "\n";
@array = (1,);
print "\n", join ", ", @array, "\n";
print "Found 0 at " . BinSearch (0, \&cmpFunc, \@array) . "\n";
print "Found 1 at " . BinSearch (1, \&cmpFunc, \@array) . "\n";
print "Found 2 at " . BinSearch (2, \&cmpFunc, \@array) . "\n";
@array = ();
print "\n", join ", ", @array, "\n";
print "Found 0 at " . BinSearch (0, \&cmpFunc, \@array) . "\n";
sub cmpFunc {
$_[0] <=> $_[1];
}
-------------- 8< --------------
1, 3, 5, 8, 10,
Use of uninitialized value in concatenation (.) or string at C:\Documents and Settings\Peter.WINDOMAIN\My Documents\PerlMonks\junk\noname.pl line 31.
Found 0 at -0.5
Found 1 at 0
Found 2 at 0.5
Found 5 at 2
Found 8 at 3
Found 10 at 4
Found 11 at 4.5
1, 3, 5, 8,
Found 0 at -0.5
Found 1 at 0
Found 2 at 0.5
Found 5 at 2
Found 8 at 3
Found 9 at 3.5
1,
Found 0 at -0.5
Found 1 at 0
Found 2 at 0.5
Found 0 at
</c>
</readmore></div>
<CODE>
sub BinSearch {
my ($target, $cmp, $array) = @_;
my $posmin = 0;
my $posmax = $#$array;
return undef if ! @array;
return -0.5 if $cmp->($array->[0], $target) > 0;
return $#$array + 0.5 if $cmp->($array->[-1], $target) < 0;
while (1) {
my $mid = int (($posmin + $posmax) / 2);
my $result = $cmp->($array->[$mid], $target);
if ($result < 0) {
$posmin = $posmax, next if $mid == $posmin && $posmax != $posmin;
return $mid + 0.5 if $mid == $posmin;
$posmin = $mid;
} elsif ($result > 0) {
$posmax = $posmin, next if $mid == $posmax && $posmax != $posmin;
return $mid - 0.5 if $mid == $posmax;
$posmax = $mid;
} else {
return $mid;
}
}
}
</CODE>