python - 二分查找递归错误: maximum recursion depth exceeded in comparison

Question

我试图在 python 中执行二分查找程序。我遵循了算法步骤，但它给了我这个错误。这是我的代码:

def binarySearch(a,k,l,r):
    
    if l > r:
        return -1
    else:
        mid = (l+(r-l))//2
        if(a[mid]>k):
            return binarySearch(a,k,l,mid-1)
        elif(a[mid]<k):
            return binarySearch(a,k,mid+1,r)
        else:
            return mid


t = int(input("Enter no. of test cases: "))
for _ in range(t):
    n,k = map(int, input().split())
    a = list(map(int, input().rstrip().split()))
    print(binarySearch(a,k,0,n))

错误:

    return binarySearch(a,k,mid+1,r)
  File "e:/Coding/Algorithms/Searching/binarySearch.py", line 10, in binarySearch
    return binarySearch(a,k,mid+1,r)
  File "e:/Coding/Algorithms/Searching/binarySearch.py", line 10, in binarySearch
    return binarySearch(a,k,mid+1,r)  [Previous line repeated 994 more times]
  File "e:/Coding/Algorithms/Searching/binarySearch.py", line 3, in binarySearch    if r < l:
RecursionError: maximum recursion depth exceeded in comparison

Answer 1

您的错误在于这一行:

    else:
        mid = (l+(r-l))//2

您需要除以(r-l)//2，然后添加l，但您正在做(l+(r-l))//2 结果是 (l+r-l)//2 == r//2。

将其更改为l + (r-l)//2。

当这个条件成立时会发生什么:

        elif(a[mid]<k):
            return binarySearch(a,k,mid+1,r)

r 保持不变，并且由于您总是在不考虑 l 的情况下除以 r，因此 mid 永远不会改变。因此，您会收到递归深度超出错误。

此外，搜索的上限为 n-1，其中 n 是数组的长度。如果函数调用中的 n 是数组的长度(从代码中看不出来)，则需要按如下方式减一:

binarySearch(a,k,0,n-1))