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