为函数找到一个只有一个输入（数组）的不动点

Question

我正在尝试使用只接受一个输入（数组）的函数在数组中找到一个固定点。问题是，我试图避免构建此函数可以调用的另一个函数。如果我能做到这一点，这种情况就会得到解决。这些数组将包含一个排序整数列表，供我遍历。我试图通过使用二进制搜索来降低它的运行时间。我已经尝试了 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

如果没有找到不动点，这个函数将return-1。

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

想知道人们可能会发现这段代码有什么问题。

Answer 1

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

Answer 2

重复我在评论中所说的内容，问题是您忘记了 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

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

为函数找到一个只有一个输入（数组）的不动点

Find a fixed point with only one input (an array) for the function

binary-search

python-3.x

fixed-point-iteration