Re: Perl comparison function for binary search



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 built-in 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 special-order certain sorts of tools at low cost and
in short order. -- Larry Wall
.