我正在尝试使用仅接受一个输入(数组(的函数在数组中找到一个固定点。问题是，我试图避免构建该函数可以调用的另一个函数。如果我能做到这一点，这种情况就会得到解决。这些数组将包含一个排序整数列表，供我迭代。我试图通过使用二进制搜索来保持其运行时较低。我已经尝试了 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]
好奇人们可能会发现此代码有什么问题。
重复我在评论中所说的，问题是你忘记了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
迭代还具有在内存方面具有较少开销(不需要调用堆栈(的好处，尽管在其他语言上，某些编译器会进行优化。
所编写的算法的根本问题是你失去了对原始数组中位置的跟踪。 当您递归时，您返回数组一半的不动点，但例如在[-4, -2, 0, 2, 4]中，当您拆分数组并在[2, 4]中找到不动点时，它不起作用，因为[2, 4]中没有不动点。 您需要将偏移量传递到每个递归调用中，以便您可以说出类似if mid + offset == a[mid].