Binary Search RecursionError: maximum recursion depth exceeded in comparison

Question

I was trying to execute the Binary Search program in python. I followed the algorithm steps yet it gives me this error. Here's my code:

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))

Error:

    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

Your error lies in this line:

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

You need to divide (r-l)//2 and then add l but you are doing (l+(r-l))//2 which results in (l+r-l)//2 == r//2.

Change it to l + (r-l)//2.

What happens is when this condition is true:

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

r stays the same and since you are always dividing r without considering l, mid never changes. So, you get a recursion depth exceeded error.

Also, the upper bound of the search is n-1 where n is the length of the array. If the n in your function call is the length of the array (it isn't obvious from the code), you need to subtract one as follows:

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

Answer 2

In case the item isn't found in the list, the recursion never converges. There are two mistakes here:

1. r's starting value should be n-1, not n
2. The calculation of mid should not subtract 1. I.e., it should be mid = (l+r)//2.

Put these together and you'll get:

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