# 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 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

.

**Follow-Ups**:**Re: Perl comparison function for binary search***From:*Nelson Castillo

**References**:**Perl comparison function for binary search***From:*Nelson Castillo

- 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):