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;
}

##</code><code>##

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

##</code><code>##

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;
    }
  }
}