2

我正在尝试使用仅接受一个输入（数组）的函数在数组中找到一个固定点。问题是，我试图避免构建该函数可以调用的另一个函数。如果我能做到这一点，这种情况就迎刃而解了。这些数组将包含一个排序整数列表供我迭代。我试图通过使用二进制搜索来保持其运行时间较低。我已经尝试了 100 种不同的方法，但都没有什么效果。

def fixed_point(a):    

    if len(a) <= 2: # tried len(a) == 0 and len(a) == 1
        return -1 

    mid = len(a)//2 # have used (len(a)-1)//2 as well

    if mid == a[mid]:
        return a[mid]

    if mid > a[mid]:
        return find_point(a[mid+1:])

    else:
        return find_point(a[:mid])

    return -1

如果没有找到固定点，此函数将返回 -1。

该函数也通过了为此构建的 10000 次测试，但由于某种原因找不到“5”是数组的不动点：[-10, -5, -2, 2, 3, 5, 7, 10, 15, 25 , 35, 78, 129]

很好奇人们可能会发现此代码有什么问题。

4

2 回答 2

1

重复我在评论中所说的话，问题是你正在失去对a.

您的方法是递归的，并且您在每次调用时传递一个大小缩小的列表。正因为如此，你要找的中间点和你最终比较的中间点是不一样的。

切换到迭代方法，您可以将内容保留在原始a.

def fixed_point(a):
    l, u = 0, len(a)

    while l <= u:
        m = (l + u) // 2
        if m == a[m]:
            return m
        elif m > a[m]:
            l = m + 1
        else:
            u = m - 1

    return -1


>>> fixed_point([-10, -5, -2, 2, 3, 5, 7, 10, 15, 25, 35, 78, 129])
5

迭代还具有内存开销较小的好处（不需要调用堆栈），尽管在其他语言上，一些编译器会进行优化。

于 2018-06-03T01:53:32.680 回答
0

所写算法的基本问题是您忘记了您在原始数组中的位置。当你递归时，你返回一半数组的不动点，但是例如[-4, -2, 0, 2, 4]当你分割数组并找到其中的不动点时，[2, 4]它不起作用，因为[2, 4]. 您需要将偏移量传递给每个递归调用，因此您可以说类似if mid + offset == a[mid].

于 2018-06-03T01:53:15.860 回答