in reply to Binary Search - revisited

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) = @_;

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