运行递归二进制搜索算法时出现分段错误

Question

所以我第一次尝试递归，在 Python 中编写了一个简单的二进制搜索算法 3. 在运行我的程序之后我得到了这个错误：调用时超出了最大递归深度一个 Python 对象我做了一些研究，它说要添加这一行：sys.setrecursionlimit(40000)

我做到了。当我输入一个不在我的列表中的数字时，我得到了这个 Segmentation Fault 错误。我读了这个 post 从我收集的 Python 深度递归耗尽内存？

我无法想象 Python 不支持深度递归？无论如何，这是我的代码：

import sys

arr = [5, 17, 23, 33, 39, 44, 58, 62, 70, 74, 82, 99]
end = len(arr)
sys.setrecursionlimit(40000)

def binarySearch(arr, start, end,  x):

   #print("This is end: {}".format(end))
    mid = int((end + start)/2)
    #print("This is start {}".format(start))
    #print("This is end {}".format(end))
    #print("This is mid {}".format(mid))

    if x == arr[mid]:
        return x
    elif (x < arr[mid]):
        start = 0
        end = mid - 1
        return binarySearch(arr, start, end, x)
    else: # if x > arr[mid]
        start = mid + 1
        end = end
        return binarySearch(arr, start, end,  x)


position = binarySearch(arr, 0, 12, 55)
print(position)

Answer 1

您的代码中有几个错误：

您没有基本案例。在进行递归之前，您应该检查是否 start > end。
start = 0确实应该是start = start，或者干脆不加。

修复这些错误，稍微清理一下代码，这有效 -

def binarySearch(arr, start, end, x):
    if start <= end:
        mid = (end + start) // 2

        if x == arr[mid]:
            return mid
        elif x < arr[mid]:
            end = mid - 1           
        else:
            start = mid + 1

        return binarySearch(arr, start, end, x)

    return -1

binarySearch(arr, 0, len(arr), 55)
-1

binarySearch(arr, 0, len(arr), 58)
6

另外请注意，对于 O(logN) 算法，您 永远不会 需要 40,000 的最大递归深度。如果您运行陷入 "maximum recursion depth exceeded" 错误，您应该首先重新评估您的算法。

运行递归二进制搜索算法时出现分段错误

Segmentation Fault when running recursive binary search algorithm

python

recursion

binary-search

python-3.x

运行 递归二进制搜索算法时出现分段错误

Segmentation Fault when running recursive binary search algorithm

python

recursion

binary-search

python-3.x

运行递归二进制搜索算法时出现分段错误