Re: Perl comparison function for binary search
 From: krahnj@xxxxxxxxx (John W. Krahn)
 Date: Sun, 13 Apr 2008 13:10:26 0700
Nelson Castillo wrote:
Hi :)
Hello,
I wrote this binary search function. I wrote it so that I could pass
a comparison function as the last parameter. But I have to write
"sub" and I noticed that the built in sort function doesn't need it.
So I have to write:
sub { shift <=> shift}
instead of:
{$a <=> b}.
This might be a silly question, but I'd like to know if I can modify the
binary search function to receive a function similar to the one that
"sort" receives.
To find out if you can do the same thing that a Perl builtin function can do you have to find out what prototype it uses:
$ perl le'print prototype "CORE::open"'
*;$@
$ perl le'print prototype "CORE::sort"'
But sort does not have a prototype so you can't replicate what sort does in perl.
perldoc f prototype
perldoc perlsub
#/usr/bin/perl w
use strict;
# By sefault it works on strings
sub binary_search {
my $arr = shift;
my $value = shift;
my $cmpf = shift  sub {shift cmp shift};
"shift cmp shift" is ambiguous (there is no guarantee which shift will be called first.) You should probably use "$_[0] cmp $_[1]" instead.
Because you only have two options, either strings or numbers, you could do it something like this:
use Scalar::Util qw/ looks_like_number /;
sub binary_search {
my $arr = shift;
my $value = shift;
my $cmpf = looks_like_number( $value )
? sub { $_[0] <=> $_[1] }
: sub { $_[0] cmp $_[1] };
my $left = 0;
my $right = @$arr  1;
That is usually written as:
my $right = $#$arr;
while ($left <= $right) {
my $mid = int($right + $left) >> 1;
The int() is superfluous. $right and $left are integers so adding them together will produce an integer.
my $c = &$cmpf($arr>[$mid], $value);
That is usually written as:
my $c = $cmpf>($arr>[$mid], $value);
if ($c == 0) {
return 1
}
if ($c > 0) {
$right = $mid  1
}
else {
$left = $mid + 1
}
}
return 0
};
my @arr = qw(1 2 3 4 5 6 7 8);
for (0 .. 9)
{
print binary_search(\@arr, $_) . "\n"
}
John

Perl isn't a toolbox, but a small machine shop where you
can specialorder certain sorts of tools at low cost and
in short order.  Larry Wall
.
 FollowUps:
 Re: Perl comparison function for binary search
 From: Nelson Castillo
 Re: Perl comparison function for binary search
 References:
 Perl comparison function for binary search
 From: Nelson Castillo
 Perl comparison function for binary search
 Prev by Date: Re: trying to use IO::Handle
 Next by Date: Re: trying to use IO::Handle
 Previous by thread: Re: Perl comparison function for binary search
 Next by thread: Re: Perl comparison function for binary search
 Index(es):
Relevant Pages
