Бесконечный цикл в двоичном поиске
Я пытаюсь реализовать двоичный поиск со следующей функцией:
def buggy_binary_search(input, key): low = 0 high = len(input)-1 mid = (low + high)/2 while low <= high: if input[mid] == key: return mid if input[mid] > key: high = mid - 1 else: low = mid return -1 Вышеуказанная функция при запуске попадает в бесконечный цикл. Как я могу это исправить?
2 Solutions collect form web for “Бесконечный цикл в двоичном поиске”
Поскольку вы не обновляете значение mid цикла while, он продолжает проверять один и тот же элемент и запускается в бесконечный цикл, чтобы исправить это, как указывали многие люди, обновить mid цикла while.
Кроме того, вы должны делать low = mid+1 а не low = mid .
Полный код приведен ниже:
def binary_search(input, key): low = 0 high = len(input)-1 mid = (low + high)/2 while low <= high: mid = (low + high)/2 if input[mid] == key: return mid if input[mid] > key: high = mid - 1 else: low = mid + 1 return -1
Убедитесь, что вход отсортирован!
def binary_search(input, key): low = 0 high = len(input)-1 mid = (low + high)/2 while low <= high: mid = (low + high)/2 if input[mid] == key: return mid if input[mid] > key: high = mid - 1 else: low = mid + 1 return -1
как сказал Дмитрий Быченко, вы должны положить mid = (низкий + высокий) / 2 в цикле.
- Форматирование переменных даты и времени дает пропущенные значения времени как 00:00:00. Использование Python
- Гомография футбольного поля