В то время как цикл не останавливается при рекурсивном двоичном поиске
Я пытаюсь запрограммировать алгоритм рекурсивного двоичного поиска на Python. Однако я продолжаю сталкиваться с бесконечным циклом while. Я боюсь, что это должно быть что-то простое, на что я не обращаю внимания, но я нигде не могу найти ответ, большинство вопросов о том, что циклы while не завершаются, используют другие условия, а не логические значения.
Алгоритм действительно работает, он печатает индекс элемента, который я ищу, или «Значение не найдено», если элемент отсутствует в списке. Но цикл while никогда не завершается, даже если я установил found = False после того, как значение было найдено / не найдено. Почему это?
def binarysearch(A, v, x, y):
found = True
while found:
if x < y:
h = (x+y) //2
if A[h] < v:
binarysearch(A, v, h+1, y)
else:
binarysearch(A, v, x, h)
elif A[x] == v:
found = False
print("Element you are looking for is at index {}".format(x))
else:
found = False
print("Value is not in array")
#Code to test the binarysearch algorithm
blist = []
for value in range(0,124):
if value % 2 ==0:
blist.append(value)
print(blist)
binarysearch(blist, 68, 0, len(blist)-1)
Ответы 2
Переменная found, которую вы изменяете с помощью found = False, - это местный для области конкретного рекурсивного вызова binarysearch. Это не экземпляр found, который вы должны изменить пытающийся, то есть тот, который находится на верхнем уровне дерева рекурсии. Таким образом, хотя цикл while в текущей области видимости завершится, циклы в областях выше не будут.
Поскольку у вас уже есть практически полная реализация цикла, вместо использования поверх него рекурсии (которая вызывает ошибку, связанную с областью действия), вы можете просто сузить диапазон поиска, перезаписав x и y.
def binarysearch(A, v, x, y):
found = True
while found:
if x < y:
h = (x+y) //2
if A[h] < v:
x = h+1 // replaced
else:
y = h // replaced
elif A[x] == v:
found = False
print("Element you are looking for is at index {}".format(x))
else:
found = False
print("Value is not in array")
Ошибка, которую я совершил, заключалась в том, что я использовал цикл while ПОВЕРХ рекурсивных вызовов, которые, по сути, являются двумя способами сделать то же самое. Для людей, заинтересованных в алгоритме, который использует рекурсию вместо цикла while, чтобы поддерживать его работу, я предоставил его рабочую версию ниже.
def binarysearch(A, v, x, y):
if x < y:
h = (x+y) //2
if A[h] < v:
binarysearch(A, v, h+1, y)
else:
binarysearch(A, v, x, h)
elif A[x] == v:
print("Element you are looking for is at index {}".format(x))
else:
print("Value is not in array")