为什么我得到 "RecursionError" 实施二进制搜索算法？

Question

我正在实施 returns:

的二进制搜索算法

如果 key 在列表中：True 和 key我在找;
如果 key 不在列表中：它 returns False

这是我的函数代码：Bin_Search (A, l, r, key)

def Bin_Search (A, l, r, key):
    
    if l == r:
        if A[l] == key:
            return True, l
        else:
            return False
        
    mid = (l+r)//2
    
    if A[mid] == key:
            return  True, mid
        
    if A[mid] < key:
        return Bin_Search(A, l, mid-1, key)
    else:
        return Bin_Search(A, mid+1, r, key)

但我遇到了麻烦，因为它有时有效，有时无效。例如，在数组 A 上实现函数以查找 key = 14

A = [35, 21, 49, 0, 46, 5, 1, 14, 50, 34]
Bin_Search (A, 0, len(A), 14)

我收到以下错误：

RecursionError                            Traceback (most recent call last)
<ipython-input-174-380483777517> in <module>
     19 
     20 A = [35, 21, 49, 0, 46, 5, 1, 14, 50, 34]
---> 21 Bin_Search(A, 0, len(A), 14)

<ipython-input-174-380483777517> in Bin_Search(A, l, r, key)
     13 
     14     if A[mid] < key:
---> 15         return Bin_Search(A, l, mid-1, key)
     16     else:
     17         return Bin_Search(A, mid+1, r, key)

<ipython-input-174-380483777517> in Bin_Search(A, l, r, key)
     15         return Bin_Search(A, l, mid-1, key)
     16     else:
---> 17         return Bin_Search(A, mid+1, r, key)
     18 
     19 

<ipython-input-174-380483777517> in Bin_Search(A, l, r, key)
     13 
     14     if A[mid] < key:
---> 15         return Bin_Search(A, l, mid-1, key)
     16     else:
     17         return Bin_Search(A, mid+1, r, key)

<ipython-input-174-380483777517> in Bin_Search(A, l, r, key)
     15         return Bin_Search(A, l, mid-1, key)
     16     else:
---> 17         return Bin_Search(A, mid+1, r, key)
     18 
     19 

... last 1 frames repeated, from the frame below ...

<ipython-input-174-380483777517> in Bin_Search(A, l, r, key)
     15         return Bin_Search(A, l, mid-1, key)
     16     else:
---> 17         return Bin_Search(A, mid+1, r, key)
     18 
     19 

RecursionError: maximum recursion depth exceeded in comparison

为什么会出现此错误？我必须修复代码的哪一部分才能正常工作？

Answer 1

def Bin_Search (A, l, r, key):
    
    if l == r:
        if A[l] == key:
            return True,l
        else:
            return False
        
    mid = (l+r)//2
    
    if A[mid] == key:
            return  True, mid
        
    if A[mid] > key:
        return Bin_Search(A, l, mid-1, key)
    else:
        return Bin_Search(A, mid+1, r, key)

#A = [35, 21, 49, 0, 46, 5, 1, 14, 50, 34]
A = [0,1,5,14,21,34,35,46,49,50]
Bin_Search (A, 0, len(A), 14)

***BIG_MISTAKE : 你应该有一个用于二进制搜索的排序列表

A = [0,1,5,14,21,34,35,46,49,50]

如果键小于中间值，你有误，你应该搜索左边而不是右边。

if A[mid] > key:
        return Bin_Search(A, l, mid-1, key)
    else:
        return Bin_Search(A, mid+1, r, key)

为什么我得到 "RecursionError" 实施二进制搜索算法？

Why do I get "RecursionError" implementing Binary Search algorithm?

python

recursion

binary-search