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

Question

I am implementing a Binary Search algorithm that returns:

In the case the key is in the list: True and the position of the key I am looking for;
In the case the key is not in the list: it returns False

Here is my code of the function: 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)

But I am having trouble since sometimes it works and sometimes not. For example, implementing the function on the array A to find key = 14

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

I get the following error:

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

Why do I get this error? Which part of the code I must fix in order that it works properly?

You can see that if your code was "def a(x): return a(x)" it would "recurse" until it ran out of stack space, hence the error. I suspect that because of the arithmetic of index calculation, you end up with a path through the code that has the same effect: Bin_Search calls Bin_Search calls Bin_Search ... You might be able to see this by printing out the arguments at the start of every call to Bin_Search. — Mark Lavin
– Mark Lavin, Commented Jul 5, 2021 at 14:39
Note that binary search only works on sorted data. Your input is not sorted. — MisterMiyagi
– MisterMiyagi, Commented Jul 5, 2021 at 14:52

r nepal · Accepted Answer · 2021-07-05 15:04:37Z

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 : You should have a sorted list for binary search

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

You have mistake in if key is less than mid value you should search for left part instead of right.

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

edited Jul 5, 2021 at 15:04

answered Jul 5, 2021 at 14:47

r nepal

364 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related