I use a version that returns the 1s complement of where the element should be inserted when the element is not found.
Furthermore, the elements to compare are in $a and $b, just like they are in sort compare functions.
Finally, the prototype I specified allows the function to be called using the sort's block syntax.
Example:
# Add $value to sorted @array, if it's not already there.
$idx = binsearch { $a <=> $b } $value, @array;
splice(@array, ~$idx, 0, $value) if ($idx < 0);
Code:
sub _unsigned_to_signed {
return unpack('i', pack('I', $_[0]));
}
sub binsearch(&$\@) {
my ($compare, $value, $array) = @_;
#
# If the $value is not found in @array,
# the 1s complement of where the $value
# should be inserted is returned. So,
# $value is found if the return value >= 0.
#
# When compare is called, $a is an alias for $value,
# and $b is an alias for the element of the array
# against which $a which be compared.
#
# Example:
# # Add $value to sorted @array, if it's not already there.
# $idx = binsearch { $a <=> $b } $value, @array;
# splice(@array, ~$idx, 0, $value) if ($idx < 0);
#
my $i = 0;
my $j = $#$array;
return $j if ($j == -1);
my $ap = do { no strict 'refs'; \*{caller().'::a'} };
my $bp = do { no strict 'refs'; \*{caller().'::b'} };
local *$ap;
local *$bp;
*$ap = \$value;
for (;;) {
my $k = int(($j-$i)/2) + $i;
*$bp = \($array->[$k]);
my $cmp = &$compare();
return $k if ($cmp == 0);
if ($cmp < 0) {
$j = $k-1;
return _unsigned_to_signed(~$k) if ($i > $j);
} else {
$i = $k+1;
return _unsigned_to_signed(~$i) if ($i > $j);
}
}
}
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.