Implémentation de la recherche binaire en Python

Question

J'essaie d'implémenter une solution en utilisant la recherche binaire. J'ai une liste de numéros

list = [1, 2, 3, 4, 6] 
value to be searched = 2 

Je vous ai écrit quelque chose comme ça

def searchBinary(list, sval): 
    low = 0 
    high = len(list) 

    while low < high: 
     mid = low + math.floor((high - low)/2) 

     if list[mid] == sval: 
      print("found : ", sval) 
     elif l2s[mid] > sval: 
      high = mid - 1 
     else: 
      low = mid + 1 

mais quand je suis en train de mettre en œuvre, je reçois une erreur comme: indice hors de portée. S'il vous plaît aider à identifier le problème.

Answer 1

Quelques petites choses.

1. Votre dénomination est incohérente. En outre, n'utilisez pas list comme nom de variable, vous surveillez le composant intégré global.

2. La condition d'arrêt est while low <= high. C'est important.

3. Vous ne cassez pas lorsque vous trouvez une valeur. Cela entraînera une récursion infinie.

---

def searchBinary(l2s, sval): # do not use 'list' as a variable 
    low = 0 
    high = len(l2s) 

    while low <= high: # this is the main issue. As long as low is not greater than high, the while loop must run 
     mid = (high + low) // 2 

     if l2s[mid] == sval: 
      print("found : ", sval) 
      return 
     elif l2s[mid] > sval: 
      high = mid - 1 
     else: 
      low = mid + 1 

Et maintenant,

list_ = [1, 2, 3, 4, 6] 
searchBinary(list_, 2) 

Sortie:

found : 2 

Answer 2

MISE À JOURhigh = len(lst) - 1 par commentaires ci-dessous.

---

Trois questions:

1. Vous avez utilisé l2s au lieu de list (le nom réel du paramètre).
2. Votre condition while doit être low <= high, et non low < high.
3. Vous devriez probablement retourner l'index lorsque la valeur est trouvée, ou None (ou peut-être -1?) Si elle n'est pas trouvée.

Quelques autres petits changements que je fait:

• C'est une mauvaise idée de cacher le intégré list. J'ai renommé le paramètre à lst, qui est couramment utilisé dans Python dans cette situation.
• mid = (low + high) // 2 est une forme plus simple de trouver le milieu.
• La convention Python est d'utiliser snake_case, pas camelCase, donc j'ai renommé la fonction.

Code fixe:

def binary_search(lst, sval): 
    low = 0 
    high = len(lst) - 1 

    while low <= high: 
     mid = (low + high) // 2 

     if lst[mid] == sval: 
      return mid 
     elif lst[mid] > sval: 
      high = mid - 1 
     else: 
      low = mid + 1 

    return None 

print(binary_search([1, 2, 3, 4, 6], 2)) # 1