La recherche binaire en utilisant la récursivité est dans une boucle infinie

Question

Je suis novice en python, donc je ne sais pas s'il me manque quelque chose d'évident (comme par exemple un deux-points ou un point quelque part). J'essaye de faire fonctionner cet algorithme de recherche binaire, mais si je passe une liste plus grande que 3 éléments, le programme passe à un freinage à récursion infinie et le maximum défini en python.

les cas de base fonctionnent bien.

Les listes [] et [element1] passent par.

[element1, element2, element3, ..., element99] se coincer ...

Voici le code:

def binsearch(pylist, element): 
    if len(pylist) == 0: 
     return False 
    elif len(pylist) == 1 and pylist[0] == element: 
     return True 
    else: 
     mid = len(pylist)/2 - 1 
     if element > pylist[mid]: 
      binsearch(pylist[mid:], element) 
     else: 
      binsearch(pylist[:mid], element) 

Merci.

Answer 1

Nous devons évidemment supposer que les données sont triées, sinon la recherche binaire est plutôt inutile. Tout d'abord, vous manquez le cas quand l'élément est égal à lui-même le pivot:

if element == pylist[mid]: 

En outre, dans ce bloc:

elif len(pylist) == 1 and pylist[0] == element: 
    return True 

Vous ne gérez pas le cas où vous avez un élément gauche et c'est pas l'élément que vous voulez, auquel cas vous devriez retourner False.

est sous le code entièrement corrigé:

def binsearch(pylist, element): 
    pylist = sorted(pylist) # Just to be sure 
    if len(pylist) == 0: 
     return False  

    if len(pylist) == 1: 
     if pylist[0] == element: 
      return True 
     else: 
      return False 
    else: 
     mid = len(pylist) // 2 
     if element == pylist[mid]: 
      return True 
     elif element > pylist[mid]: 
      return binsearch(pylist[mid:], element) 
     else: 
      return binsearch(pylist[:mid], element) 

Il y a certainement de rendre ce code plus efficace, mais cela est tout simplement corrigeons le code tel qu'il a été donné.

Answer 2

Ok, terminé. J'ai dû faire une fonction de tri à bulles pour trier une liste aléatoire sans la fonction set().

def binsearch(pylist, element): 
    if len(pylist) == 0: 
     return False 
    else: 
     v_mid = len(pylist) // 2 
     if pylist[v_mid] == element: 
      return True 
     else: 
      if element > pylist[v_mid]: 
       return binsearch(pylist[v_mid + 1:], element) 
      else: 
       return binsearch(pylist[:v_mid], element)