Ricerca binaria con ricorsione
In questo esercizio implementerai l'algoritmo di ricerca binaria che hai appena visto usando la ricorsione. Ricorda che una funzione ricorsiva è una funzione che chiama se stessa.
Questo esercizio fa parte del corso
Strutture dati e algoritmi in Python
Istruzioni dell'esercizio
- Definisci il caso base.
- Verifica se il valore da cercare è uguale al valore in mezzo.
- Chiama ricorsivamente la funzione
binary_search_recursive()sulla metà sinistra della lista. - Chiama ricorsivamente la funzione
binary_search_recursive()sulla metà destra della lista.
Esercizio pratico interattivo
Prova a risolvere questo esercizio completando il codice di esempio.
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))