Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
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 meditating upon the Monastery: (8)
As of 2014-08-27 23:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (253 votes), past polls