perl - 如何在 Perl 中实现二分查找?

标签 perl binary-search

我想在 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 );

问题是我不确定我的最后一个 else(标有 ## SEE MY QUESTION BELOW ## )是否“漂亮”。有没有更好的方法来做到这一点?

最佳答案

尽管我最初同意 Axeman 的回答……在某种程度上,它类似于我在使用线性逻辑(至少是其中的一小部分)方面的第一个(非常糟糕的)答案。具体来说,没有理由打电话$get_val_subref$mid - 1 .这是一个不必要的线性搜索步骤。

这是我的建议。除了避免线性搜索之外,它还有一个非常简单的好处:

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 中实现二分查找?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3881644/

相关文章:

c# - SOAP 响应大小

linux - Perl 5.8 : possible to get any return code from backticks when SIGCHLD in use

rust - 二进制搜索大块向量

java - 编写通用的二分查找方法

java - Arrays.BinarySearch 没有保证吗?

algorithm - 未知大小数组的二进制搜索

java - 为什么java.util.Arrays中的binarySearch()方法是使用循环实现的?

windows - Strawberry Perl——默认情况下编码转换在哪里完成?

perl - 使用 GD::Graph 绘制条形图

windows - 使用 Perl 脚本模拟按下键盘 F 键