Бинарный поиск с использованием рекурсии
В этом упражнении вы реализуете алгоритм бинарного поиска, который только что изучили, используя рекурсию. Напомним, что рекурсивная функция — это функция, которая вызывает саму себя.
Это упражнение является частью курса
Структуры данных и алгоритмы на Python
Инструкции к упражнению
- Определите базовый случай.
- Проверьте, равно ли искомое значение элементу в середине списка.
- Вызовите функцию
binary_search_recursive()рекурсивно для левой половины списка. - Вызовите функцию
binary_search_recursive()рекурсивно для правой половины списка.
Интерактивное практическое упражнение
Попробуйте выполнить это упражнение, дополнив этот пример кода.
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))