Python Binary Search while цикл не прерывается

Question

Я использую бинарный поиск на Python для решения следующей проблемы: у вас есть список из n положительных целых чисел: a0, a1, a2, ... an-1, в порядке возрастания ,

Теперь ваш друг задаст вам вопросы, каждый из которых: «Вот положительное целое число B. Является ли это частью списка?»

Если B находится в списке a, вы скажете «Да».

Ваша задача - вывести количество раз, когда вы говорите «да» для любых данных входов.

1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^5 и 1 ≤ A, B ≤ 10^9

Я написал следующий код:

n = int(raw_input()) 
a = [int(x) for x in raw_input().split()] 
m = int(raw_input()) 

answer = 0 

lo = 0 
hi = len(a) - 1 
end = False 

for i in range(0, m): 
    B = int(raw_input()) 
    while (lo <= hi): 
     mid = int((lo + hi)/2) 
     if B == a[mid]: 
      answer = answer + 1 
      break 
     elif B < a[mid]: 
      hi == mid - 1 
     elif B > a[mid]: 
      lo == mid + 1 

print answer 

я проверил его в терминале, и он просто не выводит ответа, вместо этого я просто продолжаю писать цифры (даже буквы) в терминал бесконечно. Вход для n, a, m и первого значения B был успешным, поскольку терминал дает мне сообщение об ошибке, если я набираю букву, но после первых 4 строк он просто не отвечает на все, что я набираю, пока не использовал ctrl Z, чтобы выйти из Python.

Кому-нибудь понравится, почему это так? Я также проверил эту программу вручную, и это должно было сработать.

спасибо.

Answer 1

Одна проблема с кодом так прокомментирована @JohnnyMopp: вы должны использовать = для назначения, а не == оператор равенства.

Другая проблема заключается в том, что значения для hi и low не сбрасываются после каждого бинарного поиска. Вы должны переместить строки, которые Инициализировать эти переменные внутри цикл:

answer = 0 

for i in range(0, m): 
    B = int(raw_input()) 
    lo = 0 
    hi = len(a) - 1 

    while (lo <= hi): 
     mid = int((lo + hi)/2) 
     if B == a[mid]: 
      answer = answer + 1 
      break 
     elif B < a[mid]: 
      hi = mid - 1 
     elif B > a[mid]: 
      lo = mid + 1 

print answer 

Лучшей идеей было бы написать бинарный поиск в виде функции.

---

Другим способом достижения этой цели без написания собственного двоичного поиска является использование bisect.bisect():

import bisect 

def bisect_in(l, v): 
    return v == l[bisect.bisect(l, v)-1] 

count = 0 
for i in range(m): 
    B = int(raw_input()) 
    count += bisect_in(a, B) 

print count