Problem:


Search II

You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.

Input

In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.

Output

Print C in a line.

Constraints

Elements in S is sorted in ascending order

n ≤ 100000

 q ≤ 50000 

0 ≤ an element in S ≤ 109

0 ≤ an element in T ≤ 109

Sample Input 1

5
1 2 3 4 5
3
3 4 1

Sample Output 1

3

Sample Input 2

3
1 2 3
1
5

Sample Output 2

0

Sample Input 3

5
1 1 2 2 3
2
1 2

Sample Output 3

2

Notes

Template in C
-->



Sample input:
5
1 2 3 4 5
3
3 4 1


Sample output:
3

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def find(S, x):
    left = -1
    right = n

    while right - left > 1:
        mid = (left + right)//2

        if S[mid] == x:
            return True 

        if S[mid] < x:
            left = mid
        else:
            right = mid

    return False

n = int(input())
S = sorted(map(int,input().split()))
q = int(input())
T = map(int,input().split())

count = 0
for t in T:
    if find(S, t):
        count += 1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def find(S, x):
    left = 0
    right = n

    while right - left >= 1:
        mid = (left + right)//2

        if S[mid] == x:
            return True 

        if S[mid] < x:
            left = mid + 1
        else:
            right = mid

    return False

n = int(input())
S = sorted(map(int,input().split()))
q = int(input())
T = map(int,input().split())

count = 0
for t in T:
    if find(S, t):
        count += 1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

n = int(input())
S = sorted(map(int,input().split()))
q = int(input())
T = map(int,input().split())

print(len(set(S) & set(T)))

Submission status: Accepted

Solution code:
#5.3
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

findCount = 0

for t in T:
    left = 0
    right = n
    center = right // 2
    preCenter= 0
    while left < right:
        if S[center] == t:
            findCount += 1
            break
        
        if S[center] > t:
            right = center
        else:
            left = center + 1
        
        center = (left + right) // 2

print(findCount)

Submission status: Accepted

Solution code:
a_len = int(input())
a = {n for n in input().split(" ")}
b_len = int(input())
b = {n for n in input().split(" ")}
print(len(a & b))

Submission status: Accepted

Solution code:
def main():
    n = input()
    S = map(int,raw_input().split())
    q = input()
    T = map(int,raw_input().split())
    m = 0
    for i in range(q):
        i0 = 0
        i1 = n-1
        t = T.pop()
        while i0 <= i1:
            im = int((i0+i1)/2)
            if t == S[im]:
                m += 1
                break
            elif t < S[im]:
                i1 = im-1
            elif t > S[im]:
                i0 = im+1
            
    print m


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def binary_search():
	input()
	s = set(input().split())
	input()
	t = set(input().split())
	print(len(s & t))	

if __name__ == '__main__':
	binary_search()

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
cnt = 0
for i in T:
 a = 0
 b = n-1
 while b >= a:
  mid = (a + b) // 2
  if S[mid] == i:
   cnt += 1
   break
  elif S[mid] > i:
   b = mid - 1
   continue
  else:
   a = mid + 1
   continue
print(str(cnt))

Submission status: Accepted

Solution code:
# coding=utf-8

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = map(int, input().split())
found = []

for t in T:
    left = 0
    right = n
    find_flag = False
    while True:
        search_pos = (left + right) // 2
        if t < S[search_pos]:
            right = search_pos
        elif t > S[search_pos]:
            left = search_pos + 1
        elif t == S[search_pos]:
            found.append(t)
            find_flag = True
            break
        if left == right and not find_flag:
            break

print(len(found))

Submission status: Accepted

Solution code:
len_s = int(input())
s = [int(i) for i in input().split()]
len_t = int(input())
t = [int(i) for i in input().split()]
cnt = 0


for f in t:
    key = f
    lower_bound = 0
    upper_bound = len(s)-1
    found = False

    while lower_bound <= upper_bound and not found:
        middle_pos = (lower_bound + upper_bound) // 2

        if s[middle_pos] < key:
            lower_bound = middle_pos + 1
        elif s[middle_pos] > key:
            upper_bound = middle_pos - 1
        else:
            found = True
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
S = set(map(int, input().split()))
q = int(input())
T = set(map(int, input().split()))
print(len(S)+len(T)-len(S.union(T)))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
S = tuple(map(int, input().split()))
q = int(input())
T = tuple(map(int, input().split()))
cnt = 0
for n in T:
    m = bisect.bisect_right(S, n)
    if m > 0 and S[m-1] == n:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def binary_search(S, t):
    start = 0
    end = len(S)
    while True:
        mid = start + (end-start)//2
        if S[mid] == t:
            return True
        elif (end-start) < 2:
            return False
        elif S[mid] < t:
            start = mid
        else:
            end = mid

if __name__ == "__main__":
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))
    ans = 0
    for i in T:
        if binary_search(S, i):
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input().split(" ")
S = list(map(int, s))
q = int(input())
t = input().split(" ")
T = list(map(int, t))
C = 0

def binarySearch(A, key):
    left = 0
    right = len(A)
    while left < right:
        mid = (left + right) // 2
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return False

for i in range(q):
    if binarySearch(S,T[i]):
        C += 1

print(C)

Submission status: Accepted

Solution code:
def BinarySearch(A, key):
    left = 0
    right = len(A)
    while left < right:
        mid = (left + right) // 2
        if A[mid] == key:
            return mid
        elif key < A[mid]:
            right = mid
        else:
            left = mid+1
    return -1
    
n = int(input())
S = list(map(int, input().split(" ")))
q = int(input())
T = list(map(int, input().split(" ")))

C = 0
for t in T:
    if BinarySearch(S, t) != -1:
        C += 1
print(C)

Submission status: Accepted

Solution code:
n1 = int(input())
s = (input()).split()
n2 = int(input())
t = (input()).split()
m = []

for i in range(0, n2):
      left = 0
      right = n1
      key = int(t[i])
      while left < right:
            mid = int((left + right)/2)
            if int(s[mid]) == key:
                  m.append(key)
                  break
            elif key < int(s[mid]):
                  right = mid
            else:
                  left = mid + 1

print(len(m))

Submission status: Accepted

Solution code:
#ALDS1_4-B BinarySearch
input()
S=input().split()
input()
T=input().split()
print(len(set(S)&set(T)))

Submission status: Accepted

Solution code:
n = int(input())
S = [int(i) for i in input().split()]
q = int(input())
T = [int(i) for i in input().split()]

cnt = 0
for t in T:
    low = 0
    high = len(S) - 1
    while low <= high:
        mid = (low + high) // 2
        if t == S[mid]:
            cnt += 1
            break
        elif t < S[mid]:
            high = mid - 1
        else:
            low = mid + 1
print(cnt)

Submission status: Accepted

Solution code:
def main():
	num = 0

	n = int(input())
	s_list = list(map(int, input().split()))

	_ = input()
	t_list = list(map(int, input().split()))
	for t in t_list:
		if b_search(s_list, t) != -1:
			num += 1
	
	print(num)

def b_search(li, key):
	left = 0
	right = len(li)
	while left < right:
		mid = int((left+right) / 2)
		if li[mid] == key:
			return mid
		elif key < li[mid]:
			right = mid
		else:
			left = mid + 1

	return -1

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]

cnt = 0

def binarysearch(x, l):
	mi = 0
	ma = len(l) - 1
	
	while mi < ma:
		tmp = (mi + ma) // 2
		
		if l[tmp] == x:
			return tmp
		elif l[tmp] < x:
			mi = tmp + 1
		else:
			ma = tmp - 1
	
	else:
		if mi == ma:
			if x == l[mi]:
				return mi
			else:
				return -1
		else:
			if x == l[mi]:
				return mi
			elif x == l[ma]:
				return ma
			else:
				return -1
	
	

for x in t:
	if binarysearch(x, s) != -1:
		cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
def binarySearch(t):
	left,right = 0,n
	while right > left+1:
		mid = (left+right) // 2
		if S[mid] == t:
			return True
		elif S[mid] > t:
			right = mid
		else:
			left = mid
	return False

n = int(input())
S = [int(s) for s in input().split()]
q = int(input())
T = [int(s) for s in input().split()]

print(sum([binarySearch(t) for t in T]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Binary Search
n ????????´??°???????????°??? S ??¨???q ????????°????????´??°???????????°??? T ??????????????????
T ?????????????????´??°????????§ S ?????????????????????????????° C ???????????????????????°????????????????????????????????????
"""
def bsrch(l, s, e, a):
    """ ????????????????????? """
    c = int((e - s) / 2) + s if e - s > 1 else s
    x = l[c]
#    print(l[s:e])
#    print("s:{} e:{} c:{} a:{}".format(s,e,c,a))
    if x == a:
        return True
    else:
        if c > s:
            if x < a:
                return bsrch(l, c, e, a)
            elif x > a:
                return bsrch(l, s, c, a)
    return False

def main():
    """ ????????? """
    n = int(input())
    S = list(map(int,input().split()))
    q = int(input())
    T = list(map(int,input().split()))

    cnt = {}
    for j in range(q):
       x = bsrch(S, 0, n, T[j])
       if x == True:
           cnt[T[j]] = 1
    print(len(cnt))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def binarySearch(t):
    left=0
    right=n
    while left<right:
        mid=(left+right)//2
        if S[mid]==t:
            return 1
        elif t<S[mid]:
            right=mid
        else:
            left=mid+1
    return 0

n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))

C=0

for t in T:
    C+=binarySearch(t)
    
print(C)

Submission status: Accepted

Solution code:
def binary_search(S, key):
    left = 0
    right = len(S)
    while left < right:
        mid = int((left + right) / 2)
        # ???????????£????????????????????? return
        if S[mid] == key:
            return 'Found'
        # ??????????????????????°????????????°??????????????????????????????????????´??°
        elif S[mid] > key:
            right = mid
        # ???????????????????????§???????????°???????????? + 1 ?????????????????§??????????????´??°
        elif S[mid] < key:
            left = mid + 1
    return False

if __name__ == '__main__':
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))

    cnt = 0
    for key in T:
        if binary_search(S, key):
            cnt += 1

    print(cnt)

Submission status: Accepted

Solution code:
input()
S = set(input().split())
input()
T = set(input().split())
print(len(S & T))

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = map(int, input().split())


def binarySearch(A, key):
    left = 0
    right = len(A)
    while left < right:
        mid = (left + right) // 2
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return False


a = 0
for t in T: a += binarySearch(S, t)
print(a)

Submission status: Accepted

Solution code:
n = int(raw_input())
if n > 1:
    s = map(int, raw_input().split())
else:
    s = int(raw_input())
    
q = int(raw_input())
if q > 1:
    t = map(int, raw_input().split())
else:
    t = [int(raw_input())]

# f = open('ALDS1_4_B-in8.txt', 'r')
# data = f.readlines()
# n = int(data[0])
# s = map(int, data[1].split())
# q = int(data[2])
# t = map(int, data[3].split())

def binarySearch(A, key):
    left = 0
    right = len(A)
    while left < right:
        mid = int((left + right)/2)
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return False

count = 0
for i in range(q):
    if binarySearch(s, t[i]):
        count += 1
print count

Submission status: Accepted

Solution code:
n = int(input())
S = set(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

sum = 0

for i in T:
    if i in S:
        sum +=1
        
print(sum)

Submission status: Accepted

Solution code:
input()
S = set(input().split())
input()
T = set(input().split())
count = 0
for t in T:
    if t in S:
        count += 1
print(count)

Submission status: Accepted

Solution code:
# your code goes here
#binary
n=int(input())
S=[int(i) for i in input().split()]
q=int(input())
T=[int(i) for i in input().split()]
C=0
for i in range(q):
    j=n//2
    b=n//2
    while T[i]!=S[j] and b>1:
        if b%2==1:
            b+=1
        b//=2
        if T[i]>S[j]:
            j+=b
        elif T[i]<S[j]:
            j-=b
        if j>=n:
            j=n-1
        elif j<0:
            j=0
    #    if i==25:
       #     print(b)
#            print(j)
    if T[i]==S[j]:
        C+=1
    else:
        if T[i]>S[j]:
            j+=b
        else:
            j-=b
        if T[i]==S[j]:
            C+=1
#    print(j)
print(C)

Submission status: Accepted

Solution code:
# Aizu Problem ALDS_1_4_B: Binary Search
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")


_ = input()
S = set([int(_) for _ in input().split()])
_ = input()
T = set([int(_) for _ in input().split()])
print(len(S.intersection(T)))

Submission status: Accepted

Solution code:
def search(a, x):
    n = len(a)
    hi = n-1
    lo = 0
    while hi >= lo:
        med = (hi+lo)/2
        if a[med] == x:
            return True
        elif a[med] > x:
            hi = med-1
        else:
            lo = med+1
    return False

n = int(raw_input())
S = map(int, raw_input().split(' '))
q = int(raw_input())
T = map(int, raw_input().split(' '))

found = 0
for x in T:
    if search(S, x):
        found += 1

print found

Submission status: Accepted

Solution code:
def binary_search(S, n, index ):
    if S[index] == n:
        return 'eq'
    elif S[index] < n:
        return 'bt'
    elif S[index] > n:
        return 'lt'

n = int(input())
S = [int(i) for i in input().split()]
q = int(input())
T = [int(i) for i in input().split()]

cnt = 0
for i in T:
    mini = 0
    maxi = len(S) - 1
    while int(maxi - mini) >= 0:
        index = int( (mini + maxi) / 2 )
        rs = binary_search(S, i, index )
        if rs == 'eq':
            cnt += 1
            break
        elif rs == 'bt':
            mini = index + 1
        elif rs == 'lt':
            maxi = index - 1

print(cnt)

Submission status: Accepted

Solution code:
s = input()
snum = set(map(int, input().split()))
q = input()
qnum = set(map(int, input().split()))
print(len(snum & qnum))

Submission status: Accepted

Solution code:
s = input()
snum = set(map(int, input().split()))
q = input()
qnum = list(map(int, input().split()))
c = 0
for i in qnum:
    if i in snum:
        c += 1

print(c)

Submission status: Accepted

Solution code:
# your code goes here
#binary search function
def bi(B0,bA,BI):
    bm=bA[1]+bA[2]
    bm//=2
    if BI[bA[1]]<=B0<=BI[bm]:
        bA=[0,bA[1],bm]
    else:
        bA=[0,bm,bA[2]]
   # print(bA)
    return bA
def bs(B0,BI):
    if B0<BI[0]:
        bA=[0,0,0]
    elif B0>BI[-1]:
        bA=[0,-1,-1]
    else:
        bA=[0,0,len(BI)-1]
        while bA[2]-bA[1]>1:
            bA=bi(B0,bA,BI)
        if B0==BI[bA[1]]:
            bA=[1,bA[1]]
        elif B0==BI[bA[2]]:
            bA=[1,bA[2]]
        else:
            bA=[0,bA[1],bA[2]]
   # print(bA)
    return bA
n=int(input())
S=[int(i) for i in input().split()]
q=int(input())
T=[int(i) for i in input().split()]
c=0
for i in range(q):
    bA=bs(T[i],S)
    if bA[0]==1:
        c+=1
print(c)

Submission status: Accepted

Solution code:
import sys

def binary_search(array, num, left, right):
    if right < left + 1:
        return False
    center = (right + left) / 2
    if array[center] == num:
        return True
    elif array[center] < num:
        return binary_search(array, num, center + 1, right)
    elif array[center] > num:
        return binary_search(array, num, left, center)

n = int(sys.stdin.readline().strip())
S = map(lambda x: int(x), sys.stdin.readline().strip().split(" "))
n = int(sys.stdin.readline().strip())
T = map(lambda x: int(x), sys.stdin.readline().strip().split(" "))

res = 0

for t in T:
    if binary_search(S, t, 0, len(S)):
        res += 1

print res

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
count = 0

Sm, SM = S[0], S[n - 1]
for x in T:
    if x < Sm or SM < x:
        continue
    l, r = 0, n - 1
    while l <= r:
        m = (l + r) // 2
        if S[m] == x:
            count += 1
            break
        elif S[m] > x:
            r = m - 1
        else:
            l = m + 1
print(count)

Submission status: Accepted

Solution code:
def binarySearch(A, key):
    left = 0
    right = len(A)

    while left < right:
        mid = (left + right) / 2
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1 

    return False


n = int(raw_input())
S = map(int, raw_input().split())

q = int(raw_input())
T = map(int, raw_input().split())

ans = 0

for i in T:
    if binarySearch(S, i):
        ans += 1

print ans

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

ans = 0
for tmp_t in T:
    left = 0
    right = n
    while(left<right):
        mid = (left + right)//2
        if S[mid]==tmp_t:
            ans += 1
            break
        elif S[mid]>tmp_t:
            right = mid
        else:
            left = mid+1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = set(raw_input().split())
q = int(input())
T = set(raw_input().split())
print len(S&T)

Submission status: Accepted

Solution code:

n = int(input())
s = list(map(lambda x:int(x), input().split()))
q = int(input())
t = list(map(lambda x:int(x), input().split()))
c = 0

for i in t:
    left = 0
    right = n
    mid = lambda x,y:(x + y)/2
    while left < right:
        if s[int(mid(left,right))] == i:
            c += 1
            break
        elif s[int(mid(left,right))] > i:
            right = int(mid(left,right))
        else:
            left = int(mid(left,right)) + 1

print(c)

Submission status: Accepted

Solution code:

n = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]
c = 0

for i in t:
    left = 0
    right = n
    mid = lambda x,y:(x + y)/2
    while left < right:
        if s[int(mid(left,right))] == i:
            c += 1
            break
        elif s[int(mid(left,right))] > i:
            right = int(mid(left,right))
        else:
            left = int(mid(left,right)) + 1

print(c)

Submission status: Accepted

Solution code:
n = int(input())
s = set(map(int,input().split()))
q = int(input())
t = set(map(int,input().split()))

print(len(s & t))

Submission status: Accepted

Solution code:
def binarySearch(array,search,left,right):
    mid = int(left + (right - left)//2)
    while right - left > 1:
        if array[mid] <= search:
            left = mid
            mid = int(left + (right - left)//2)
        else:
            right = mid
            mid = int(left + (right - left)//2)
    if array[mid] == search: return mid
    else: return -1

n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))
count = 0

for t_tmp in t:
    bs = binarySearch(s,t_tmp,0,len(s))
    if bs != -1:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))
count = 0

def binarySearch(x,s):
    left = 0
    right = len(s)

    while left < right:
        mid = (left + right) // 2
        if s[mid] == x:
            return mid
        elif x < s[mid]:
            right = mid
        else:
            left = mid+1
    return -1

for x in t:
    if binarySearch(x,s) != -1:
        count += 1
print(count)

Submission status: Accepted

Solution code:
def binarySearch(e, n, A):
    if e<A[0] or e>A[-1]:
        return False
    l, r = 0, n
    while l<=r:
        m = (r+l)//2
        if m == r or m == l:
            return False
        if e == A[m]:
            return True
        elif e < A[m]:
            r = m
        else:
            l = m
    return False


def ALDS1_4B():
    n, S = int(input()), list(map(int, input().split()))
    q, T = int(input()), list(map(int, input().split()))
    print(sum([1 for e in T if binarySearch(e, n, S)]))


if __name__ == '__main__':
    ALDS1_4B()

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

count = 0
for item in t:
    middle = int((n - 1) / 2)
    upper = n - 1
    lower = 0
    while(True):
        if s[middle] == item:
            count += 1
            break
        elif lower >= upper:
            break
        elif s[middle] > item:
            upper = middle
            middle = int((lower + lower) / 2)
        elif s[middle] < item:
            lower = middle + 1
            middle = int((upper + lower) / 2)

print(count)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import sys


def binary_search(data, targets, n):
    cnt = 0
    for num in targets:
        small = 0
        big = n - 1
        while small < big:
            index = (small + big) >> 1
            if small < big:
                if num < data[index]:
                    big = index - 1
                if num > data[index]:
                    small = index + 1
                if num == data[index]:
                    cnt += 1
                    break
        if small == big and num == data[small]:
            cnt += 1

    return cnt


if __name__ == "__main__":
    input_data = [val.split() for val in sys.stdin.read().splitlines()]
    n = int(input_data[0][0])
    data = [int(n) for n in input_data[1]]
    targets = [int(n) for n in input_data[3]]
    print(binary_search(data, targets, n))

Submission status: Accepted

Solution code:
def binary_search(A, key):
    left = 0
    right = len(A)

    while left < right:
        mid = (left + right) // 2
        if (A[mid] == key):
            return 1
        elif (key < A[mid]):
            right = mid
        else:
            left = mid + 1
    return 0

def main():
    n = int(input())
    s = list(map(int, input().split()))
    q = int(input())
    t = list(map(int, input().split()))

    res = 0
    for i in t:
        a = binary_search(s, i)
        res += a

    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

def lower_bound(lis, target):
    left, right = 0, n  # NOT n-1 !!!!!!!!!!
    while left<right:
        mid = (left+right)//2
        if lis[mid]==target:
            return True
        elif target<lis[mid]:
            right = mid
        else:
            left = mid+1
    return False

cnt = 0
for i in range(q):
    cnt = cnt+1 if lower_bound(s, t[i]) else cnt
print(cnt)

Submission status: Accepted

Solution code:
n = raw_input()
S = map(int, raw_input().split())
q = raw_input()
T = map(int, raw_input().split())

def BinarySearch(list, num):
	left = 0
	right = len(list) - 1
	while left <= right:
		mid = (left + right) / 2
		#print("left = {:}".format(left))
		#print("mid = {:}".format(mid))
		#print("right = {:}".format(right))
		#print("")
		if list[mid] == num:
			return 1
		elif list[mid] < num:
			left = mid + 1
			#print("left = {:}".format(left))
			#print("mid = {:}".format(mid))
			#print("right = {:}".format(right))
			#print("")
		else:
			right = mid - 1
			#print("left = {:}".format(left))
			#print("mid = {:}".format(mid))
			#print("right = {:}".format(right))
			#print("")
	return 0

cnt = 0
for i in T:
	cnt += BinarySearch(S, i)

print cnt

Submission status: Accepted

Solution code:
n = input()
S = map(int, raw_input().split())
q = input()
T = map(int, raw_input().split())

def b_search(key):
    left = 0
    right = n
    while( left < right ) :
        mid =  (left + right) // 2

        if ( key == S[mid] ):
            return 1
        if ( key > S[mid] ):
            left = mid + 1 
        if ( key < S[mid] ):
            right = mid
    return 0

if __name__ == "__main__":
    ans = 0
    for i in T:
        if b_search(i) == 1:
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:


def bin_search(arr, x):
    n = len(arr)
    left = 0
    right = n
    while left < right:
        m = (left + right) / 2
        key = arr[m]
        if key == x:
            return True

        if x < key:
            right = m
        elif x > key:
            left = m + 1

    return False


def solve():
    num_s = int(raw_input())
    s = map(int, raw_input().split(" "))
    num_t = int(raw_input())
    t = map(int, raw_input().split(" "))

    count = 0
    for x in t:
        if bin_search(s, x):
            count += 1

    print count


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())

S = list(map(int, input().split(" ")))

q = int(input())

T = list(map(int, input().split(" ")))

def binary_search(target, key):
    left = 0
    right = len(S)

    while(left < right):
        mid = (left + right) // 2
        if S[mid] == key:
            return True
        elif S[mid] < key:
            left = mid + 1
        else:
            right = mid

    return False

cnt = 0
for t in T:
    if binary_search(S, t): cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
S = set(input().split())
q = int(input())
T = set(input().split())

print(len(S&T))

Submission status: Accepted

Solution code:
n = int(input())
S = set(input().split())
q = int(input())
T = set(input().split())

print(len(S & T))

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
 
count = 0
for key in T:
    left = 0
    right = n
    while left < right:
        mid = (right + left) // 2
        if S[mid] == key:
            count = count + 1
            break
        if key < S[mid]:
            right = mid
        else:
            left = mid + 1
print(count)

Submission status: Accepted

Solution code:
import sys


def binsearch(x, s):
    l = 0
    r = len(s)
    while (l < r):
        m = int((l + r) / 2)
        if s[m] == x:
            return True
        else:
            if s[m] < x:
                l = m + 1
            else:
                r = m
    return False


ns = sys.stdin.readline()
s = [int(i) for i in sys.stdin.readline().split()]
nt = sys.stdin.readline()
t = [int(i) for i in sys.stdin.readline().split()]

cnt = 0
for x in t:
    if binsearch(x, s):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n=int(raw_input())
s=(raw_input()).split(" ")
q=int(raw_input())
t=(raw_input()).split(" ")

for i in range(n):
    s[i]=int(s[i])
for i in range(q):
    t[i]=int(t[i])
t=sorted(t)

#print(s)
#print(t)

s_index=0

rt=0

for i in range(q):
    while s[s_index]<=t[i]:
        #print("s_index="+str(s_index)+" s[s_index]="+str(s[s_index]))
        #print("i="+str(i)+" t[i]="+str(t[i]))
        #print("rt="+str(rt))
        #print(" ")
        if s[s_index]==t[i]:
            rt+=1
            break
        s_index+=1
        if s_index>=n:
            break
        
    if s_index>=n:
            break

print(rt)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = map(int, input().split())

    ans = 0
    for t in T:
        if binsearch(t, S):
            ans += 1

    print(ans)


def binsearch(x, xs):
    left = 0
    right = len(xs)
    mid = (left + right) // 2

    while left < right:
        if x == xs[mid]:
            return True
        elif x < xs[mid]:
            right = mid
        else:
            left = mid + 1
        mid = (left + right) // 2

    return False

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def search(target, array):
	start,end=0,len(array)-1
	while (start+1<end):
		mid = (start + end) // 2
		if array[mid] == target:
			return 1
		elif array[mid] < target:
			start = mid
		elif array[mid] > target:
			end = mid

		if array[start] == target:
			return 1
		if array[end] == target:
			return 1
	return 0		

input()
userinput=input()
array=[int(s) for s in userinput.split(' ')]
#print(len(array))
input()
userinput=input()
searcharray=[int(s) for s in userinput.split(' ')]
count =0
for s in searcharray:
	count+=search(s,array)
print(count)

Submission status: Accepted

Solution code:
def search(S,n,T):
    L=0
    R=n

    while L<R:
        M=int((L+R)/2)
        if T>S[M]:
            L=M+1
        elif T<S[M]:
            R=M
        elif T==S[M]:
            return 1
    return 0

sum=0

n=int(input())
S=list(map(int, input().split()))

q=int(input())
T=list(map(int, input().split()))

for i in range(0,q):
    if search(S,n,T[i])==1:
        sum+=1

print(sum)

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    N = int(input())
    S = tuple(map(int, input().split()))
    Q = int(input())
    T = tuple(map(int, input().split()))

    counter = Counter(S)
    cnt = 0
    for i in T:
        cnt += any([counter[i]])
    print(cnt)

main()

Submission status: Accepted

Solution code:
def main():
    global N, S
    N = int(input())
    S = tuple(map(int, input().split()))
    Q = int(input())
    T = tuple(map(int, input().split()))

    cnt = 0
    for i in T:
        cnt += binsearch(i)
    print(cnt)

def binsearch(key):
    left = 0
    right = N
    while left < right:
        mid = (left + right) // 2
        if key == S[mid]:
            return 1
        if key > S[mid]:
            left = mid + 1
        else:
            right = mid
    return 0

main()

Submission status: Accepted

Solution code:
input()
S = set(input().split())
input()
T = set(input().split())
print(len(S & T))