Sunny Xu Sunny Xu - 1 month ago 13
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())

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


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.

Answer

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

print answer

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