Recherche binaire avec récursion

Dans cet exercice, vous allez implanter l'algorithme de recherche binaire que vous venez d'apprendre en utilisant la récursion. Rappelez‑vous qu'une fonction récursive est une fonction qui s'appelle elle‑même.

Cette activité fait partie du cours

Structures de données et algorithmes en Python

Voir le cours

Instructions de l’exercice

Définissez le cas de base.
Vérifiez si la valeur recherchée est égale à la valeur au milieu.
Appelez récursivement la fonction binary_search_recursive() sur la moitié gauche de la liste.
Appelez récursivement la fonction binary_search_recursive() sur la moitié droite de la liste.

Exercice interactif pratique

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

def binary_search_recursive(ordered_list, search_value):
  # Define the base case
  if ____(ordered_list) == 0:
    return False
  else:
    middle = len(ordered_list)//2
    # Check whether the search value equals the value in the middle
    if search_value == ____:
        return True
    elif search_value < ordered_list[middle]:
        # Call recursively with the left half of the list
        return ____(ordered_list[:middle], search_value)
    else:
        # Call recursively with the right half of the list
        return ____
  
print(binary_search_recursive([1,5,8,9,15,20,70,72], 5))

Modifier et exécuter le code