如何在Perl中實現二進制搜索？

Question

我想在Perl中實現二進制搜索算法。我的'數組'按降序排列（不是一個實際的數組，而是一個獲取索引並返回值的函數）。問題在於可能存在延伸的相同值。如果我的搜索值處於這樣的範圍內，我想返回包含它的第一個索引。

這是我寫：

# get_val should be a *decreasing* function for idexes $i in min..max, 
# formally: for any $i,$j s.t. $max>=$i>$j>=$min : 
# $get_val_subref($i, $extra) <= $get_val_subref($j, $extra) 
# min and max are the inclusive boundaries for the search 
# get_val sub should get an index in min..max and an extra data reference, and return 
# the value for the given index 
# returns the smallest index $i in min..max for which $get_val_subref($j, $extra) 
# returns $searched_val, or undef if no such index exists 
sub binary_search { 
    my ($min, $max, $searched_val, $get_val_subref, $get_val_sub_extra_data) 
     = @_; 
    my ($mid, $val); 
    while ($min <= $max) { 
     $mid = $min + int(($max - $min)/2); 
     $val = $get_val_subref->($mid, $get_val_sub_extra_data); 

     if ($val > $searched_val) { 
      $min = $mid + 1; 
     } 
     elsif ($val < $searched_val) { 
      $max = $mid - 1; 
     } 
     else { ## SEE MY QUESTION BELOW ## 

      # surely $val == $searched_val, but is it the first one? 

      if ( $mid > $min 
       and $get_val_subref->($mid - 1, $get_val_sub_extra_data) 
       == $searched_val) 
      { 

       # $val == $searched_val and prev($val) == $searched_val 
       # we have to continue 
       $max = $mid - 1; 
      } 
      else { 

       # $val == $searched_val and prev($val) != $searched_val 
       # wer'e done 
       return $mid; 
      } 
     } 
    } 

    # $val was not found. return undef 
    return undef; 

} 

，這是使用它一個簡單的例子：

sub get_val_sub { 
    my ($pos, $a) = @_; 
    my $val = $a->[$pos]; 
    return $val; 
} 

my @arr = (80, 40, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0); 
say "RET:", binary_search(0, $#arr, 0, \&get_val_sub, \@arr); 

的問題是我不知道我還有最後一個（標有## SEE MY QUESTION BELOW ## ）是「漂亮」。有沒有更好的方法來做到這一點？

Answer 1

儘管我最初同意Axeman的回答......它在很小的一個方面與使用線性邏輯（至少是它的一小部分）的第一個（非常糟糕的）答案類似。具體而言，沒有理由使用$mid - 1與$get_val_subref聯繫。這是一個不必要的線性搜索步驟。

這是我的建議。除了避免線性搜索，所以它具有非常簡單的好處：

sub binary_search { 
    ... 
    my ($mid, $val, $solution); 
    while ($min <= $max) { 
     ... 
     else { 
      $solution = $mid; # Store a possible solution. 
      $max = $mid - 1; # But continue with the binary search 
           # until $min and $max converge on each other. 
     } 
    } 
    return $solution; 
} 

Answer 2

雖然我第一次帶FM的答案，那你展示（所有的零）的情況下同意是不是一個線性的一個很好的例子後退搜索。雖然我不喜歡你只是繼續二進制搜索，「第一個x」確實有一個可計算的值，並且仍然具有亞線性能，而線性反向搜索具有 - 的當然 - 一個線性之一。

所以我喜歡你的想法，但它更緊​​湊是這樣的：

else { 
    return $mid unless 
     ( $mid > $min 
     and $get_val_subref->($mid - 1, $get_val_sub_extra_data) 
      == $searched_val 
     ); 
    $max = $mid - 1; 
} 

直線向後搜索是的容易計算，但作爲價值的功能變得越來越複雜，越少的計算更好。

Answer 3

您可能正在尋找Newton's approximation method。