Syntactic Confectionery Delight PerlMonks

### Binary search

by GrandFather (Sage)
 on Oct 26, 2005 at 20:24 UTC 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;
}
}
}
```
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?)

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.

Create A New User
Node Status?
node history
Node Type: snippet [id://503154]
help
Chatterbox?

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (9)
As of 2017-07-28 11:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (428 votes). Check out past polls.