二进制搜索——在使用严格引用时不能使用字符串“1”作为符号引用

Question

我一直在浏览有关此错误消息的已回答问题。

我正在尝试解决 Rosalind web site 中使用二进制搜索查找某些索引的问题。

当我的子例程找到数字时，它似乎忽略了它，如果我尝试打印 $found 变量，它会给我错误

Can't use string "1" as a symbol ref while strict refs is in use

代码是这样

sub binarysearch
{
  my $numbertolook = shift;
  my @intarray=@_;
  my $lengthint = scalar @intarray;
  my @sorted = sort {$a <=> $b} @intarray;
  #print $numbertolook, " " , @sorted, "\n";
  my $low=0;
  my $high=$lengthint-1;
  my $found =undef;
  my $midpoint;
     while ($low<$high)
     {
     $midpoint=int(($low+$high)/2);
     #print $midpoint, " ",$low," ", $high, " ", @sorted, "\n";
        if ($numbertolook<$sorted[$midpoint])
        {
            $high=$midpoint;
        }
        elsif ($numbertolook>$sorted[$midpoint])
        {
           $low=$midpoint;
        }
        elsif ($numbertolook==$sorted[$midpoint])
        {
           $found=1;
           print $found "\n";
           last;
        }
        if ($low==$high-1 and $low==$midpoint)
        {
            if ($numbertolook==$sorted[$high])
            {
                $found=1;
                print $found "\n";
                last;
            }
            $low=$high;
        }

     }

  return $found;

}

Answer 1

你想要

print $found, "\n";

或

print $found . "\n";

$found 和换行符之间没有运算符，它认为 $found 是打印换行符的文件句柄，并且因为它不是文件句柄而出错。

Answer 2

如果您调用 print 时使用多个参数，并用 space 分隔，则 print 期望第一个参数是文件句柄。这被解释为来自 documentation.

的 print FILEHANDLE LIST

print $found "\n";

你想要做的是用 , 分开，将其称为 print LIST。

print $found, "\n";

或连接为字符串，也称为 print LIST，但在 LIST.

中只有一个元素

print $found . "\n";

Answer 3

我会尽力帮助

首先，二分查找虽然看起来很简单，但很难正确编码。主要原因是它是一个错误的温床，这些错误非常普遍，以至于它们有自己的 Wikipedia page

问题是一个包含值 A 到 Z 的数组将有 26 个元素，索引为 0 到 25。我认为 FORTRAN 逆势而行，Lua，但几乎所有其他语言都在索引零处具有数组的第一个元素

在您开始使用 divide and conquer algorithms 之前，零基础对所有事情都适用。 Merge Sort 和 Binary Search 就是这样的算法。二分查找

是上半场吗？
如果是，则进一步搜索上半部分
否则进一步搜索下半部分

困难的部分是您必须决定何时找到该对象，或者何时需要放弃寻找。将数据分成两半很容易。知道何时停止是困难

它对排序的数据非常有效，但是在实现它时会出现问题，如果我们做得好，我们必须处理各种超出零或一的奇怪索引基数。

假设我有一个数组

my @alpha = 'A' .. 'Q'

如果我 print scalar @alpha 我会看到 17，这意味着数组有 17 个元素，索引从 0 到 16

现在我在那个数组中寻找 E，所以我进行二分查找，所以我想要 @alpha 的 "first half" 和 "second half"。如果我将 0 加到 16 上除以 2，我会得到一个整洁的“8”，所以中间元素位于索引 8 处，即 H

等等。有 17 个元素，这是一个奇数，所以如果我们说前八个 (A .. H) 在中间左边，最后八个 (I .. Q) 在中间的右边那么 "middle" 肯定是 I?

事实上，这都是骗人的，因为无论我们如何划分数据，二分查找都可以工作。在这种情况下，binary 表示两个部分，虽然如果这些部分的大小相等，搜索会更有效率，但算法运行并不是必需的。所以它可以是前三分之一和后三分之二，或者只是第一个元素和其余的

这就是为什么使用 int(($low+high)/2) 没问题。它向下舍入到最接近的整数，因此我们的 17 元素数组 $mid 是可用的 8 而不是 8.5

但是您的代码仍然需要考虑一些意想不到的事情。在我们的 17 元素数组的情况下，我们计算出中间索引为 8。因此索引 0 .. 7 是 "first half"，而 8 .. 16 是 "second half"，中间索引是下半场开始的地方

但是我们不是把向下的除法舍入了吗？那么在元素数量为奇数的情况下，我们的中点不应该在上半场的末尾，而不是下半场的开始吗？这是一个神秘的差一错误，但让我们看看它是否仍然适用于简单的偶数元素

@alpha = `A` .. `D`

开始和索引是0和3；中间索引是 int((0+3)/2) == 1。所以前半部分是 0..1，后半部分是 2 .. 3。工作正常

但还有很多。假设我必须搜索包含两个元素 X 和 Y 的数组。它有两个清晰的一半，我正在寻找中间之前的 A。所以我现在在单元素列表 X 中搜索 A。目标数组的最小和最大元素均为零。中点是 int((0+0)/2) == 0。接下来会发生什么？

当我们在同一列表中搜索 Z 时，情况类似但更糟。代码必须完全正确，否则我们要么搜索数组末尾，要么一次又一次地检查最后一个元素

把最坏的留到最后，假设

my @alpha = ( 'A', 'B, 'Y, 'Z' )

我正在寻找 M。以免丢失涉及检查的各种优化，这些优化可能在普通情况下要慢得多

由于所有这些，使用库或语言的内置函数来完成所有这些是迄今为止最好的解决方案。特别是，Perl 的散列通常是您检查特定字符串和任何相关数据所需的全部内容。使用的算法比任何非平凡数据集的二分搜索都要好得多

维基百科显示 this algorithm 迭代二进制搜索

The binary search algorithm can also be expressed iteratively with two index limits that progressively narrow the search range.

   int binary_search(int A[], int key, int imin, int imax)
   {
     // continue searching while [imin,imax] is not empty
     while (imin <= imax)
       {
         // calculate the midpoint for roughly equal partition
         int imid = midpoint(imin, imax);
         if (A[imid] == key)
           // key found at index imid
           return imid;
         // determine which subarray to search
         else if (A[imid] < key)
           // change min index to search upper subarray
           imin = imid + 1;
         else        
           // change max index to search lower subarray
           imax = imid - 1;
       }
     // key was not found
     return KEY_NOT_FOUND;
   }

这是您的代码的一个版本，它远非没有错误，但可以达到您的预期。你离得不远

use strict;
use warnings 'all';

print binarysearch( 76, 10 .. 99 ), "\n";

sub binarysearch {

    my $numbertolook = shift;
    my @intarray     = @_;
    my $lengthint    = scalar @intarray;
    my @sorted       = sort { $a <=> $b } @intarray;

    my $low   = 0;
    my $high  = $lengthint - 1;
    my $found = undef;
    my $midpoint;

    while ( $low < $high ) {
        $midpoint = int( ( $low + $high ) / 2 );

        #print $midpoint, " ",$low," ", $high, " ", @sorted, "\n";
        if ( $numbertolook < $sorted[$midpoint] ) {
            $high = $midpoint;
        }
        elsif ( $numbertolook > $sorted[$midpoint] ) {
            $low = $midpoint;
        }
        elsif ( $numbertolook == $sorted[$midpoint] ) {
            $found = 1;
            print "FOUND\n";
            return $midpoint;
        }

        if ( $low == $high - 1 and $low == $midpoint ) {
            if ( $numbertolook == $sorted[$high] ) {
                $found = 1;
                print "FOUND\n";
                return $midpoint;
            }
            return;
        }

    }

    return $midpoint;
}

输出

FOUND
66

二进制搜索——在使用严格引用时不能使用字符串“1”作为符号引用

Binary search—Can't use string "1" as a symbol ref while strict refs is in use

perl

binary-search

输出