Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Binary search

by GrandFather (Cardinal)
on Oct 26, 2005 at 20:24 UTC ( #503154=snippet: print w/ replies, xml ) Need Help??

Description:

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

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
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;
    }
  }
}
Comment on Binary search
Select or Download Code
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?)

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.

Back to Snippets Section

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: snippet [id://503154]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (7)
As of 2014-12-29 13:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (188 votes), past polls