Бесконечный цикл в двоичном поиске

Я пытаюсь реализовать двоичный поиск со следующей функцией:

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

Вышеуказанная функция при запуске попадает в бесконечный цикл. Как я могу это исправить?

Поскольку вы не обновляете значение 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 в цикле.

Бесконечный цикл в двоичном поиске

поиск отсортированных элементов в отсортированной последовательности