Pesquisa binária usando recursão
Neste exercício, você implementará o algoritmo de pesquisa binária que acabou de aprender usando recursão. Lembre-se de que uma função recursiva se refere a uma função que chama a si mesma.
Este exercício faz parte do curso
Estruturas de dados e algoritmos em Python
Instruções de exercício
- Defina o caso base.
- Verifique se o valor da pesquisa é igual ao valor no meio.
- Chame a função
binary_search_recursive()recursivamente na metade esquerda da lista. - Chame a função
binary_search_recursive()recursivamente na metade direita da lista.
Exercício interativo prático
Experimente este exercício preenchendo este código de exemplo.
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))