超短迷你 binary search 算法

由於需要處理插入排序的問題,小弟臨時寫了個 Perl 的 binary search 的算法,好像可以用但不知道對不對,有興趣者幫忙看看。算法如下:

=item binarysearch(\@array, \&cmpfunc, \$object)
Lazy binary search using recursive function.
Just copy the code to your source any start enjoy it.

Usage:
  my ($pos, $found) = &binarysearch(\@array, sub { $_[0] <=> $_[1] }, \$keyword);

The $low, $high bound is usage for recursive calling.  From the beginning,
it should be 0, $#array.

@param $array array reference.
@param $cmpfunc a function of result of $_[0] <=> $_[1].
@param $object target object reference to search.
@param $low lower bound, should be started with 0.
@param $high upper bound, should last item index of @array.
@return (position, found) the position in array if from or insertion position.
  found will be 1 if exact match record in array.
=cut
sub binarysearch() {
  my ($array, $cmpfunc, $object, $low, $high) = @_;
  $low = 0 if !defined $low;
  $high = $#{$array} if !defined $high;
  # reach edge
  return ($low, 0) if $high < $low;
  return ($high, 0) if $low > $high;
  my $mid = $low + int(($high - $low + 1) / 2);
  # compare
  my $state = &$cmpfunc( $object, @{$array}[$mid] );
  if ($state >= 1) {
    return &binarysearch($array, $cmpfunc, $object, $mid + 1, $high);
  } elsif ($state <= -1) {
    return &binarysearch($array, $cmpfunc, $object, $low, $mid - 1);
  } else {
    return ($mid, 1);
  }
}

 

調用方法例子: my ($pos, $found) = &binarysearch(\@array, sub { $_[0] <=> $_[1] }, \$keyword); 當中 @array 為查找的數據的 reference,裏面已經按順序排好。$cmpfunc 是一個函數,判別兩個值的大小的算法。keyword 是你需要尋找的數據,類型必須跟@array的類型一致。

返回值為一個含有兩個元素的數組,第一個元素為位置,這個位置可以用於數據維護函數 splice。

由於使用了遞歸方式,所以20行不到便寫完,連我自己都不相信行得通,所以大家必須測試,有錯留個言,小弟不“包生仔”。注意遞歸就不會快,只是算法簡單,估計10萬個元素就可能到頂了(堆棧爆炸而死)。