2

我试图在 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
4

2 回答 2

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保持不变，因为你总是在r不考虑的情况下分开l，所以mid永远不会改变。所以，你会得到一个超出递归深度的错误。

n-1此外，搜索的上限是n数组的长度。如果n函数调用中的 是数组的长度（从代码中看不出来），则需要减去一个，如下所示：

binarySearch(a,k,0,n-1))
于 2021-12-21T08:50:25.957 回答
1

如果在列表中找不到该项目，则递归永远不会收敛。这里有两个错误：

  1. r的起始值应该是n-1，而不是n
  2. 的计算不mid应该减去1。即，它应该是mid = (l+r)//2。

把这些放在一起，你会得到：

def binarySearch(a,k,l,r):

    if l > r:
        return -1
    else:
        mid = (l+r)//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
于 2021-12-21T08:57:12.430 回答