Pourquoi ma fonction de recherche binaire récursive ne retourne rien?

Question

(... ne demandez pas sur les valeurs de tableau, ce sont des marques alimentaires latino-américaines qui sont devenues des blagues avec des amis).

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

Ce programme fait exactement ce que je pensais à faire - il affiche ceci:

5 Pitusas 
2 La Bichy 
3 Manaos 

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

Cependant, ce que je reçois quand je commenter toutes les déclarations d'impression de l'avoir de retour idx ou None à la place, puis remplacer les appels avec print(binSearch(myArray, "Manaos")) et print(binSearch(myArray, "Coca-Cola")):

None 
None 

Il est évidemment censé re tourner 3 et False mais il ne retourne rien. Qu'est-ce que je fais mal?

Answer 1

Vous n'êtes pas retournerez:

return binSearch(arr, i, lower, idx) 

Vous devez également retourner dans vos 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