Sunny Xu - 1 year ago 106
Python Question

# Python Binary Search while loop doesn't break

I am using binary search on Python to solve the following problem: you have a list of n positive integers: a0, a1, a2, ... an-1, in increasing order.

Now, your friend is going to ask you m questions, each of the form, "Here is a positive integer B. Is B a part of the list?"

If B is in the list a, you will say "Yes".

Your task is to output the number of times you say yes for any given inputs.

1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5 and 1 ≤ A, B ≤ 10^9

I wrote up the following code:

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

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]:
break
elif B < a[mid]:
hi == mid - 1
elif B > a[mid]:
lo == mid + 1

``````

I tested it out in terminal, and it just never outputs an answer, instead, I just keep writing in numbers (even letters) into the terminal endlessly. Input for n, a, m, and the first value of B has been successful since terminal gives me error message if I type a letter, but after the first 4 lines, it just doesn't respond to whatever I type, until I used ctrl Z to break out of Python.

Would anyone please address why this is the case? I have tested out this program by hand as well, and it should have worked.

Thank you.

One problem with the code is as commented by @JohnnyMopp: you should use `=` for assignment, not `==` the equality operator.

Another problem is that the values for `hi` and `low` are not reset after each binary search. You should move the lines that initialise those variables inside the for loop:

``````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]:
break
elif B < a[mid]:
hi = mid - 1
elif B > a[mid]:
lo = mid + 1

``````

A better idea would be to write the binary search as a function.

Another way of achieving this without writing your own binary search is to use `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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download