Binary search

Given a search target, compare function ref and a sorted list ref, BinSearch performs a binary search on the list for the target and returns:

-0.5 if the target is less than any item in the list
items - 0.5 if the target is greater than any item in the list
the item number if target matches an item in the list
lower item number + 0.5 if target is between two items in the list

use strict;
use warnings;

my @array1 = (1, 3, 5, 8, 10);

print ((join ", ", @array1) . "\n");
print "Found 0 at " . BinSearch (0, \&cmpFunc, \@array1) . "\n";
print "Found 1 at " . BinSearch (1, \&cmpFunc, \@array1) . "\n";
print "Found 2 at " . BinSearch (2, \&cmpFunc, \@array1) . "\n";
print "Found 5 at " . BinSearch (5, \&cmpFunc, \@array1) . "\n";
print "Found 8 at " . BinSearch (8, \&cmpFunc, \@array1) . "\n";
print "Found 10 at " . BinSearch (10, \&cmpFunc, \@array1) . "\n";
print "Found 11 at " . BinSearch (11, \&cmpFunc, \@array1) . "\n\n";

my @array2 = (1, 3, 5, 8,);

print ((join ", ", @array2) . "\n");
print "Found 0 at " . BinSearch (0, \&cmpFunc, \@array2) . "\n";
print "Found 1 at " . BinSearch (1, \&cmpFunc, \@array2) . "\n";
print "Found 2 at " . BinSearch (2, \&cmpFunc, \@array2) . "\n";
print "Found 5 at " . BinSearch (5, \&cmpFunc, \@array2) . "\n";
print "Found 8 at " . BinSearch (8, \&cmpFunc, \@array2) . "\n";
print "Found 9 at " . BinSearch (9, \&cmpFunc, \@array2) . "\n";


sub cmpFunc
{
my ($index, $arrayRef, $target) = @_;
my $item = $$arrayRef[$index];

return $item <=> $target;
}
[download]

Prints:

1, 3, 5, 8, 10
Found 10 at 4
Found 0 at -0.5
Found 1 at 0
Found 2 at 0.5
Found 5 at 2
Found 8 at 3
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
[download]

sub BinSearch
{
my ($target, $cmp) = @_;
my @array = @{$_[2]};

my $posmin = 0;
my $posmax = $#array;

return -0.5 if &$cmp (0, \@array, $target) > 0;
return $#array + 0.5 if &$cmp ($#array, \@array, $target) < 0;

while (1)
  {
  my $mid = int (($posmin + $posmax) / 2);
  my $result = &$cmp ($mid, \@array, $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;
    }
  }
}
[download]

Comment on Binary search Select or Download Code

Replies are listed 'Best First'.
Re: Binary search by graff (Chancellor) on Oct 27, 2005 at 01:51 UTC
This makes really perfect, wonderful sense. Thank you. (I just noticed that "Snippet" nodes don't seem to provide the ability to move them to the "front page" -- what's up with that, I wonder?)	[reply]
Re^2: Binary search by GrandFather (Saint) on Oct 27, 2005 at 02:01 UTC
The question has been asked, but without any useful answer. Perhaps it should be asked again in Perl Monks Discussion? Perl is Huffman encoded by design.	[reply]
Re: Binary search by zby (Vicar) on Oct 27, 2005 at 12:19 UTC
I would use a cmp function with two arguments - this way it would be compatible with the cmp and sort standard library functions.	[reply]