1

我正在尝试实现二进制搜索。这是我的代码： 

#!/usr/bin/perl
#use strict;
use warnings;

@array = (1..100);
$number = <STDIN>;
$low = 0;
$high = $#array;

while($low < $high){
    print "Searcing $low ---- $high \n";
    $mid = $low + ($high - $low)/2;
    if($array[$mid] == $number){
        print "Found in index:" . $mid;
        last;
    }
    elsif($array[$mid] < $number){
        $low = $mid + 1;
    }
    else{
        $high = $mid - 1;
    }   
}

但它不起作用，尽管它是一个直接的实现（至少它会在 Java 中）。
似乎我在划分时得到浮点值并且无法搜索。如果我提供作为输入5，我会得到垃圾： 

5  
Searcing 0 ---- 99  
Searcing 0 ---- 48.5  
Searcing 0 ---- 23.25  
Searcing 0 ---- 10.625  
Searcing 0 ---- 4.3125  
Searcing 3.15625 ---- 4.3125

我怎样才能使它使用整数，以便我可以索引数组？
此外，如果我取消注释use strict，我会收到以下错误。他们的意思是什么？ 

Global symbol "@array" requires explicit package name at D:\Development\Perl\chapter3\binarySearch.pl line 6.  
Global symbol "$number" requires explicit package name at D:\Development\Perl\chapter3\binarySearch.pl line 9.  
Global symbol "$low" requires explicit package name at
4

6 回答 6

6 
my $int = int 5 / 2;
print $int;

打印 2。

于 2013-04-10T20:38:43.687 回答
3

两个深奥的解决方案。除非您真的很无聊或其他什么，否则不要实际使用这些。

  1. use integer-- 强制 Perl 将所有数值视为整数的编译指示。它可以在本地范围内，因此不会破坏程序中的所有数据

    while($low < $high){
    print "Searcing $low ---- $high \n";
    {
        use integer;
        $mid = $low + ($high - $low)/2;
    }
    if($array[$mid] == $number){
        print "Found in index:" . $mid;
        last;
    }
    elsif($array[$mid] < $number){
        $low = $mid + 1;
    }
    else{
        $high = $mid - 1;
    }   
}

  2. Perl 有一些特殊的变量$=, $-, 并且$%只保存整数值，不管你给它们赋值什么。直接使用它们

    $- = $low + ($high - $low) / 2;
if ($array[$-] == $number) { ...

    或作为中间体

    my $mid = $- = $low + ($high - $low) / 2;
if ($array[$mid] == $number) { ...

    使用像这样的魔法变量对于打代码和激怒你的同事来说很方便，但除此之外就没什么了。

于 2013-04-11T04:55:42.163 回答
2

你的代码有很多问题。

  • 你禁用了 strict。

    大概是因为下一个问题。

  • 您没有声明任何变量，使用myorour甚至use vars.

    our @array = 1..100;
use vars qw'$mid $low $high';
my $number = <STDIN>

  • 你太担心溢出了。这不是C。

    如果你的数字会溢出一个整数，它就会变成一个浮点数。

    my $mid = $low + ($high - $low)/2;

    应该只是：

    my $mid = ($high + $low)/2;

  • 您期望除法中的整数。

    my $mid = ($high + $low)/2;

    如果你真的想要一个整数，只需使用int.

    my $mid = int( ($high + $low)/2 );

  • 您没有从末尾删除换行符$number

    chomp($number);

  • 你有一个错误。

    while($low < $high){

    真的应该

    while($low <= $high){

    这确实是您的主要问题。

#! /usr/bin/env perl
use strict;
use warnings;

my @array = 1..100;
my $number = <STDIN>;
chomp $number;
my $low = 0;
my $high = $#array;

while($low <= $high){
    my $mid = int( ($high + $low)/2 );
    printf "Searching %2d .. (%2d) .. %2d\n", $low, $mid, $high;
    if($array[$mid] == $number){
        print "Found $number at index mid $mid\n";
        last;
    }elsif($array[$mid] < $number){
        $low = $mid + 1;
    }else{
        $high = $mid - 1;
    }
}

不过，这并不是真正的 Perlish。

#!/usr/bin/perl
use strict;
use warnings;
use List::MoreUtils qw'first_index';

my @array = 1..100;
my $number = <STDIN>;
chomp $number;

my $index = first_index { $_ == $number } @array;
print "Found $number at index ", $index if $index != -1;

或者更奇怪的是

#! /usr/bin/env perl
use strict;
use warnings;

my @array = 1..100;
my $number = <STDIN>;
chomp $number;

my $char = join '', map chr, @array;

my $index = index $char, chr $number;
print "Found $number at index $index\n" if $index != -1;

UV这适用于最大或较小的数字(2 ** 72) - 1。
在 64 位版本上为 18,446,744,073,709,551,615，在 32 位版本上为 4,294,967,295。

于 2013-04-11T19:17:35.970 回答
2

使用好旧的>> 1而不是/2.

例子：

perl -e 'BEGIN { print 5/2, " : ", 5>>1}'

输出：

2.5 : 2

并使用（备用减法）：

my $mid = ($low + $high) >> 1;
于 2013-04-10T23:44:06.540 回答
2

您应该使用函数int。

除此之外，您需要use strict;并使用my来确定变量的范围。这将捕获您可能错过的错误。只需像这样声明它们：

my @array = (1..100);
chomp(my $number = <STDIN>);
my $low = 0;
my $high = $#array;

my $mid = int ($low + ($high - $low)/2);

您也可以考虑使用chomp从输入中删除换行符。

于 2013-04-10T20:43:29.050 回答
1

首先，

my $mid = $low + ($high - $low)/2

可以简化为

my $mid = ($high + $low)/2;

您可以使用int

my $mid = int( ($high + $low)/2 );

或者您可以利用位移是整数除以 2 的事实。

my $mid = ($high + $low) >> 1;

另请参阅：灵活的二进制搜索功能

于 2013-04-10T23:44:06.523 回答