Implémenter la recherche binaire

Dans cette vidéo, vous avez appris à implémenter la recherche linéaire et la recherche binaire, et vous avez vu leurs différences.

Dans cet exercice, vous devez implémenter la fonction binary_search(). Saurez-vous y parvenir ?

Cet exercice fait partie du cours

<cours>Structures de données et algorithmes en Python</cours>

Voir le cours

Instructions de l’exercice

Vérifiez si la valeur recherchée est égale à la valeur au milieu.
Vérifiez si la valeur recherchée est inférieure à la valeur au milieu.
Affectez à last la valeur de middle moins un.

Exercice interactif pratique

Essayez cet exercice en complétant ce code d’exemple.

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1
  
  while first <= last:
    middle = (first + last)//2
    # Check whether the search value equals the value in the middle
    if ____ == ____:
      return True
    # Check whether the search value is smaller than the value in the middle
    elif ____ < ____:
      # Set last to the value of middle minus one
      ____
    else:
      first = middle + 1
  return False
  
print(binary_search([1,5,8,9,15,20,70,72], 5))

Modifier et exécuter le code