#python #recursion
#питон #рекурсия
Вопрос:
Я в замешательстве, почему после выполнения и выполнения условия функция не возвращает -1, а вместо этого продолжает выполнение оператора else.
если len(arr) == 1 и arr[mid] != n: возвращает -1
заданный массив = [2, 3, 4, 10, 40] и если:
- x = 1 -gt; -1 (ОК)
- x = 5 -gt; 1 (индекс, неверно)
- x = 50 -gt; 3 (индекс, неверно)
- если x находится в списке, функция возвращает правильный индекс
Когда я запускаю отладчик, в конечном итоге массив уменьшается до 1 элемента, но оператор if работает не так, как я ожидаю. Где моя ошибка, спасибо?
def binary_search(arr, n): # if n not in arr: # return -1 mid = len(arr) // 2 if len(arr) == 1 and arr[mid] != n: return -1 elif n == arr[mid]: return mid elif n lt; arr[mid]: return binary_search(arr[:mid], n) else: return mid binary_search(arr[mid:], n) Ответ №1:
ваш оператор else добавляет индекс средней точки к возвращаемому значению binary_search. Поэтому, как только вы доберетесь до последнего элемента, вы вернете -1 вверх по стеку, а затем добавите возвращаемое значение в среднюю точку предыдущего стека, которая была равна 1. Таким образом, вы затем возвращаете -1 1, что равно 0, поэтому вы возвращаете 0 в последний стек, где средняя точка была 2, поэтому вы возвращаете 2 0, что равно 2.
def binary_search(arr, n): # if n not in arr: # return -1 mid = len(arr) // 2 if len(arr) == 1 and arr[mid] != n: return -1 elif n == arr[mid]: return mid elif n lt; arr[mid]: return binary_search(arr[:mid], n) else: return binary_search(arr[mid:], n) print(binary_search( [2, 3, 4, 10, 40], 11)) -1 Комментарии:
1. Если я правильно понимаю, каждый раз, когда (в моем коде) выполняется оператор else, среднее значение помещается в стек, как только я перехожу к базовому варианту, возвращается сумма всех значений в стеке -1. Это правда?
Ответ №2:
После ответа Криса Дойла я изменил функцию следующим образом, и теперь она, похоже, работает правильно:
def binary_search(arr, n, idx=0): mid = len(arr) // 2 if len(arr) == 1 and arr[mid] != n: return -1 elif n == arr[mid]: return idx mid elif n lt; arr[mid]: return binary_search(arr[:mid], n, idx) else: return binary_search(arr[mid:], n, idx mid)