Le programme de recherche binaire ne fonctionne pas comme prévu. Qu'est-ce qui ne va pas?

Question

Je reçois la valeur "Aucun" dans mon programme? Où est-ce que je me suis trompé?

lis2 = [1, 3, 6, 2, 5, 4, 8, 12] 
lis2 = sorted(lis2) 
start = 0 
end = len(lis2) 
mid = (start+end)/2 

def binary_search(i): 
    global mid,start,end 
    if i==lis2[mid]: 
     return "Found" 
    elif i<lis2[mid]: 
     end = mid-1 
     mid = (start+end)/2 
    elif i>lis2[mid]: 
     start = mid+1 
     mid = (start+end)/2 
    else: 
     return "Not Found" 

    binary_search(i) 


print(binary_search(6)) 

Toute aide est appréciée. Merci d'avance!

Answer 1

Trois erreurs sont présentes -

• D'abord comme mentionné dans le commentaire et l'un des la réponse que vous avez écrite - binary_search(i) au lieu de return binary_search(i)
• Deuxième est une erreur logique. Votre code se déroulera en boucle infinie si les éléments ne sont pas présents dans la liste. Pour éviter cela, vérifiez si start > end, si ti se produit, alors l'élément n'est pas présent.
• Troisièmement vous initialisé end à len(lis2), cela donnera IndexError: list index out of range si vous essayez de rechercher un élément qui n'est pas présent dans la liste et est supérieur à l'élément max dans la liste (disons 23). Donc, changer end = len(lis2)-end = len(lis2)-1

code correct -

lis2 = [1, 3, 6, 2, 5, 4, 8, 12] 
lis2 = sorted(lis2) 
start = 0 
end = len(lis2)-1 
mid = int((start+end)/2) 

def binary_search(i): 
    global mid,start,end 
    if(start>end): 
     return "Not Found" 
    if i==lis2[mid]: 
     return "Found" 
    elif i<lis2[mid]: 
     end = mid-1 
     mid = int((start+end)/2) 
    elif i>lis2[mid]: 
     start = mid+1 
     mid = int((start+end)/2) 
    return binary_search(i) 

print(binary_search(6)) 

Answer 2

à la fin de votre fonction, vous devez retourner le résultat lorsque vous appelez la fonction recursivley:

def binary_search(i): 
global mid,start,end 
if i==lis2[mid]: 
    return "Found" 
elif i<lis2[mid]: 
    end = mid-1 
    mid = (start+end)/2 
elif i>lis2[mid]: 
    start = mid+1 
    mid = (start+end)/2 
else: 
    return "Not Found" 

return binary_search(i) # <----- EDITED