Бинарный поиск: бесконечный цикл

Question

Я пытаюсь решить проблему двоичного поиска, однако продолжаю получать бесконечный цикл, поскольку значения lo hi и mid не меняются, как они предполагают.Я пытаюсь найти минимальное среднее значение, где функция count_lines(mid,k) >= n.Я потратил часы на отладку этого кода, но все еще не мог понять, что не так со значениями lo hi и mid.Может ли кто-нибудь посмотреть на мой код и показать, почему это произошло?Большое спасибо!

Неудачный тестовый случай, где: n=9 k=2 Вот мой код:

   def count_lines(v,k):
   ...
   ...
   return count_lines #count_lines is an integer` 


   def binarySearch_v(n, k):
   lo = 0
   hi = n
   mid = (lo + hi)//2
   while (lo <= hi):
     if (count_lines(mid, k) < n):
        lo = mid
     elif (count_lines(mid, k) > n):
        hi = mid
     elif (count_lines(mid, k) >= n and count_lines(mid-1, k) < n):
        return mid
     mid = (lo + hi) // 2

    def main():
      print(binarySearch_v(n,k)) # Failed at n=9 & k=2
    main()

Answer 1

Вот ваше условие завершения:

while (lo <= hi):

А вот где lo и hi могут изменить значения:

lo = mid
...
hi = mid

Логический вывод заключается в том, что если этот кодзацикливаясь достаточно много раз, вы получите lo == hi.mid затем будет установлено среднее значение двух, что равно им обоим, и именно там останутся все три переменные.И как таковой цикл не завершится .Есть два возможных решения: либо изменить способ переназначения lo или hi, либо изменить условие завершения на < вместо <=.