C代码的Python翻译不起作用

Question

我想使用分治法在 O(log N) 时间内找到数组中的最大元素。我在 planet-source-code 找到了工作代码.我将它翻译成 Python 如下:

def largest(arr,i,j):
    global max1
    global max2
    if i == j:
        max1 = arr[i]
    else:
        if i == j-1:
           max1 = arr[i] if arr[i] > arr[j] else arr[j]
        else:
              mid = (i+j)/2
              largest(arr,i,mid)
              max2 = max1
              largest(arr,mid+1,j)
              if max2 > max1:
             max1 = max2

当我使用数组[98,5,4,3,2,76,78,92]，并将代码调用为

max1 = arr[0]
largest(arr,1,8)

我收到越界列表索引错误。但是 C 代码返回正确的结果 98。谁能发现我在做什么错误？

Answer 1

对于一般的未排序数组，您永远无法在小于 O(n) 的时间内找到 max。非常简单的证明:如果你在不到 O(n) 的时间内完成，那么对于一个足够大的数组，你没有足够的时间来检查每个元素。因此，对手可以将最大值放在您不检查的元素中，从而使您的算法不正确。

原始代码的优点是使用少于 2n 次的比较同时找到两者最大值和最小值(就像天真的实现会做的那样)——它使用大约 1.5n 次比较，因为它只执行当有两个元素时进行一次比较。使用它仅查找最大值不会给您带来任何好处:您最好在 Python 中使用 max(arr)(这也会更快，因为它没有函数调用开销)。

原始代码将值存储在a[1]到a[n]中，这需要一个大小为n+1的数组.因此，您应该在第一个位置放置一个虚拟元素。

但是，更麻烦的是，您的翻译不正确。原始版本使用全局变量来实现多值返回(这是一种令人难以置信的 hacky 方法)，并使用局部变量来保存旧的全局变量。由于您将 max1 和 max2 设为全局，因此该函数无论如何都不会产生正确的答案。

Python 的正确翻译是使用元组的直接多值返回:

def minmax(arr, i, j):
    if i==j:
        return arr[i], arr[i]
    elif i==j-1:
        if arr[i] < arr[j]:
            return arr[i], arr[j]
        else:
            return arr[j], arr[i]
    else:
        mid = (i+j)//2
        min1, max1 = minmax(arr, i, mid)
        min2, max2 = minmax(arr, mid+1, j)
        if min2 < min1: min1 = min2
        if max2 > max1: max1 = max2
        return min1, max1