Python 바이너리 검색 while 루프가 끊어지지 않습니다

Question

파이썬에서 다음과 같은 문제를 해결하기 위해 이진 검색을 사용하고 있습니다 : a0, a1, a2, ... an-1의 순서로 증가하는 n 개의 양수리스트가 있습니다. .

이제 친구가 "여기 양의 정수입니다. B가 목록의 일부입니까?"라는 질문에 대해 질문 할 것입니다.

B가 목록에있는 경우 "예"라고 말합니다.

귀하의 작업은 주어진 입력에 대해 '예'라고 대답 한 횟수를 출력하는 것입니다.

1 ≤ N I 다음 코드 쓴 9

10^10^5 및 1 ≤ A, B ≤ ≤ 10^5, 1 ≤ m ≤ :

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 줄 이후에는 입력 할 때까지 응답하지 않습니다. Python에서 벗어나려면 Ctrl 키를 누릅니다.

아무도 언급하지 않으시겠습니까? 나는이 프로그램을 손으로 시험해 보았고 효과가 있었음에 틀림 없다.

감사합니다.

Answer 1

@ JohnnyMopp는 코드에 대한 한 가지 문제점을 지적합니다. =을 할당에 사용해야하며, 같음 연산자는 ==이 아니어야합니다.

또 다른 문제점은 각 이진 검색 후에 hi 및 low의 값이 재설정되지 않는다는 것입니다. for 루프 내에서 변수를 초기화하는 줄을 이동해야합니다.

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 

더 좋은 방법은 이진 탐색을 함수로 작성하는 것입니다. 1 '- ->'안녕하세요 = 중간 - 1 ''에 대한 동일 보라

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