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

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

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 в цикле.

    Python - лучший язык программирования в мире.