Why is my recursive binary search function not returning anything?

Question

(...don't ask about the array values, they're Latin American food brands that became inside jokes with some friends).

def binSearch(arr, i, lower=0, upper=None):
    if upper is None:
        upper = len(arr)+1
    idx = (lower+upper)//2
    if arr[idx] == i:
        print(idx, arr[idx],'\n')
        #return idx
    elif arr[idx] != i and upper-lower<2:
        print("Not found \n")
        #return False
    elif arr[idx] < i:
        print(idx, arr[idx])
        binSearch(arr, i, idx, upper)
    elif arr[idx] > i:
        print(idx, arr[idx])
        binSearch(arr, i, lower, idx)

myArray = ["Chabona", "F-Nandito VII", "La Bichy", "Manaos", "Martín y Enzo", "Pitusas", "Trompis", "Ugi's", "VAMOS MANAOS", "Villamanaos"]

binSearch(myArray, "Manaos")
binSearch(myArray, "Coca-Cola")

This programme does exactly what I expected it to do – it outputs this:

5 Pitusas
2 La Bichy
3 Manaos 

5 Pitusas
2 La Bichy
1 F-Nandito VII
Not found

However, this is what I get when I comment out all the print statements to have it return idx or None instead, and then replace the calls with print(binSearch(myArray, "Manaos")) and print(binSearch(myArray, "Coca-Cola")):

None
None

It's obviously supposed to return 3 and False but it returns nothing. What am I doing wrong?

Padraic Cunningham · Accepted Answer · 2015-02-27 17:28:02Z

4

You are not returning:

return binSearch(arr, i, lower, idx)

You also need to return in your conditions:

def binSearch(arr, i, lower=0, upper=None):
    if upper is None:
        upper = len(arr)+1
    idx = (lower+upper)//2
    if arr[idx] == i:
        print(idx, arr[idx],'\n')
        return idx # return 3/idx
    elif arr[idx] != i and upper-lower<2:
        print("Not found \n")
        return False  # return False
    elif arr[idx] < i:
        print(idx, arr[idx])
        return binSearch(arr, i, idx, upper)
    elif arr[idx] > i:
        print(idx, arr[idx])
        return binSearch(arr, i, lower, idx)

print(binSearch(myArray, "Manaos"))
print(binSearch(myArray, "Coca-Cola"))

5 Pitusas
2 La Bichy
3 Manaos 

3
5 Pitusas
2 La Bichy
1 F-Nandito VII
Not found 

False

edited Feb 27, 2015 at 17:28

answered Feb 27, 2015 at 17:22

Padraic Cunningham

181k30 gold badges264 silver badges327 bronze badges

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

3 Comments

reggaelizard Over a year ago

Thank you, this worked! If I understood right, this means my recursive calls were running the function but since they didn't return the value it didn't 'reach' the main call, doesn't it?

Padraic Cunningham Over a year ago

You were not returning anything so like any other function if you don't specify a return value it will return None by default .

Padraic Cunningham Over a year ago

python tutor is helpful to see what is happening pythontutor.com/visualize.html#mode=display

Collectives™ on Stack Overflow

Why is my recursive binary search function not returning anything?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related