Sunny Xu - 5 months ago 28

Python Question

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
```