Почему моя функция рекурсивного поиска не работает?
Мне нужно написать простую рекурсивную функцию, которая просматривает массив от индекса: слева до индекса: справа. Нам не нужно беспокоиться о недопустимых левых и правых входных данных, которые всегда правильны. Если в массиве есть значение, равное ключу, он возвращает индекс этого значения. Если ключа нет в массиве, возвращается -1.
Я действительно не знаю, почему моя функция не работает. Я думаю, что должен. Это работает, только если ключ является первым индексом массива.
def binary_search_recursive(array: List[int], left: int, right: int,
key: int) -> int:
if left <= right:
if array[left] == key:
return left
else:
binary_search_recursive(array, left + 1, right, key)
return -1
Контрольная работа:
binary_search_recursive([0,1,5,6,23,45], 0, 5, 5)
Должен вернуться:
2
Возвращает:
-1
Это не бинарный поиск. Это бинарный поиск, использующий рекурсию для перечисления каждого элемента.
Да, это называется линейным поиском, когда вы идете по элементу, пока не найдете его. В бинарном поиске вы ищете половину списка, затем половину этой половины и так далее...
Ответы 3
Вам нужно сделать вкладку во втором возврате. Пытаться:
key: int) -> int:
if left <= right:
if array[left] == key:
return left
else:
binary_search_recursive(array, left + 1, right, key)
return -1 #Moved to the right.
Не исправляет. Все еще возвращает -1
Чтобы исправить свой код, вам нужно вернуть оператор else:
def binary_search_recursive(array: list[int], left: int, right: int,
key: int) -> int:
if left <= right:
if array[left] == key:
return left
else:
return binary_search_recursive(array, left + 1, right, key)
return -1
Но все же это не бинарный поиск.
Обновлено: Настоящий бинарный поиск выглядит примерно так:
def binary_search_recursive(array: list[int], left: int, right: int,
key: int) -> int:
if right >= left:
center = (right + left) // 2
if array[center] == key:
return center
elif array[center] > key:
return binary_search_recursive(array, left, center - 1, key)
else:
return binary_search_recursive(array, center + 1, right, key)
return -1
Вам нужно вернуть результат рекурсивного вызова binary_search_recursive():
binary_search_recursive(array, left + 1, right, key)
должно быть
return binary_search_recursive(array, left + 1, right, key)
Обратите внимание, что это нет алгоритм бинарного поиска; вы перечисляете один элемент за раз (используя рекурсию), так что это действительно последовательный поиск.
Ваша else-ветка должна
return binary_search_recursive(...). Он должен возвращать все, что возвращает рекурсивный вызов.