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.


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


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

In reply to Re: Binary Search - revisited by ikegami
in thread Binary Search - revisited by GrandFather

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.