python why does function never reach return statement?

November 19, 2022

I always get the output None instead of False

My code:

def bi_search(elements: list, x) -> bool:
    i = len(elements)/2-1
    i = int(i)
    print(i)
    if i == 0:
        return False
    elif x == elements[i]:
        return True
    elif x < elements[i]:
        e = elements[0:i + 1]
        bi_search(e, x)
    elif x > elements[i]:
        e = elements[i+1:len(elements)]
        bi_search(e, x)

commands:

my_list = [1, 2, 5, 7, 8, 10, 20, 30, 41, 100]
print(bi_search(my_list, 21))

Output:

4
1
0
None

I don’t get it, it even says that is i = 0 right before the statement, so why do I not get False as a result?

>Solution :

It’s because when you fall into 3rd or 4th case and the bi_search() recursively calls itself you forgot to take into account that the call will eventually return and the flow will continue from there further. And because you miss return for these cases, python reaches ends of the function and got nothing more to do. And since caller expected the return value but received nothing, you see None.

Your code should look this way:

def bi_search(elements: list, x) -> bool:
    i = len(elements)/2-1
    i = int(i)
    print(i)
    if i == 0:
        return False
    elif x == elements[i]:
        return True
    elif x < elements[i]:
        e = elements[0:i + 1]
        return bi_search(e, x)
    elif x > elements[i]:
        e = elements[i+1:len(elements)]
        return bi_search(e, x)

and then the output is as expected: