Sha256: 76dc977a881e106523a24bbae1948a1789cbeb333b3019c2e2440551c4974f34
Contents?: true
Size: 1.36 KB
Versions: 73
Compression:
Stored size: 1.36 KB
Contents
package BinarySearch;
use strict;
use warnings;
use Scalar::Util qw(looks_like_number);
=item binary_search
interface for binary search, produces a comparison function
so that binary_search can work on numbers and strings
maintains assertion that the array to search much be sorted in
order for binary_search to work properly
On success: returns the index in the array @A where the value $key was found
On failure: returns undef ( an invalid array index )
=cut
sub binary_search {
my ($key, $A) = @_;
my $cmp_func = looks_like_number($key)
? sub { $_[0] <=> $_[1] }
: sub { $_[0] cmp $_[1] };
my @sorted = sort { $cmp_func->($a, $b) } @$A;
foreach my $i ( 0 .. $#sorted ) {
die "Binary Search can only be performed on sorted data"
unless $cmp_func->($sorted[$i], $A->[$i]) == 0;
}
return _binary_search(
$key,
0,
scalar @$A - 1,
$cmp_func,
$A
);
}
sub _binary_search {
my ($key, $start, $end, $cmp_func, $A) = @_;
return undef
if $start > $end;
my $mid = $start + int(($end - $start) / 2);
my $c = $cmp_func->($A->[$mid], $key);
if ( $c > 0 ) {
return _binary_search($key, $start, $mid - 1, $cmp_func, $A);
}
elsif ( $c < 0 ) {
return _binary_search($key, $mid + 1, $end, $cmp_func, $A);
}
else {
return $mid;
}
}
1;
Version data entries
73 entries across 73 versions & 1 rubygems