如何在Perl中实现二进制搜索？

概述我想在Perl中实现二进制搜索算法.我的’数组’按递减顺序排序(不是实际数组,而是获取索引并返回值的函数).问题是可能存在一系列相同的值.如果我的搜索值在这样的范围内,我想返回包含它的第一个索引. 这就是我写的： # get_val should be a *decreasing* function for idexes $i in min..max,# formally: for any $i @H_301_6@ 我想在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 existssub 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); say "RET:",binary_search( 0,$#arr,\&get_val_sub,\@arr );

问题是我不确定我的最后一个(标有## SEE MY QUESTION BELOW ##)是“漂亮的”.有没有更好的方法呢？

解决方法 虽然我最初同意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;}

总结

以上是内存溢出为你收集整理的如何在Perl中实现二进制搜索？全部内容，希望文章能够帮你解决如何在Perl中实现二进制搜索？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。