simple binary search algorithm not working for some reason

Moataz Abdelraouf 0
Viewed 21

I wanted to write a simple binary search algorithm just for practice. However, it doesn't seem to work. I have NO IDEA why its not working. If anyone can help me out, I'd really appreciate that.

def binarysearch(arr, k):
    if k not in arr:
        return -1
    n = len(arr)
    mdpt = int((n-1)/2)
    if arr[mdpt] == k:
        return mdpt
    elif arr[mdpt] > k:
        binarysearch(arr[0:mdpt+1], k)
    else:
        binarysearch(arr[mdpt:n], k)

arr = [1, 2, 3, 4, 5]
k = 2
print(binarysearch(arr, k))
binary-search search recursion python
1 Answers

What is the problem?

The problem is that in the recursive case, you are not returning anything.

While you are trying to do a recursive research, when the recursive function will execute, the code will proceed, resulting into the ending of the function and the return of None.

Example

def factorial(n):
    if n == 1:
        return 1
    else:
        n*factorial(n-1)

in this case, recursive approach is ok but the factorial function is not returning anything.

In your case

In your case, the problem is in this part of the function:

if arr[mdpt] == k:
    return mdpt
elif arr[mdpt] > k:
    binarysearch(arr[0:mdpt+1], k)
else:
    binarysearch(arr[mdpt:n], k)

here binarysearch(arr[0:mdpt+1], k) and binarysearch(arr[mdpt:n], k) does return a value, but the original function doesn't return the value.

How can you fix it?

You can fix it just by returning the called function:

if arr[mdpt] == k:
    return mdpt
elif arr[mdpt] > k:
    return binarysearch(arr[0:mdpt+1], k)
else:
    return binarysearch(arr[mdpt:n], k)
XxJames07-0
Related