Recherche binaire par récursivité
Dans cet exercice, vous allez mettre en œuvre l'algorithme de recherche binaire que vous venez d'apprendre en utilisant la récursivité. Rappelez-vous qu'une fonction récursive est une fonction qui s'appelle elle-même.
Cet exercice fait partie du cours
Structures de données et algorithmes en Python
Instructions
- Définir le scénario de référence.
- Vérifiez si la valeur recherchée est égale à la valeur du milieu.
- Appelez la fonction
binary_search_recursive()de manière récursive sur la moitié gauche de la liste. - Appelez la fonction
binary_search_recursive()de manière récursive sur la moitié droite de la liste.
Exercice interactif pratique
Essayez cet exercice en complétant cet exemple de code.
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))