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:
from bisect import bisect_left

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

count = 0
for t in T:
    index = bisect_left(S, t)
    if index < len(S) and S[index] == t:
        count += 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 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()))

ans=0
for i in range(len(t)):
    ind=binarySearch(s, t[i])
    if(ind!=-1):
        ans+=1
print(ans)

Submission status: Accepted

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

count = 0
for t in T:
    min_idx = 0
    max_idx = len(S) - 1
    while min_idx <= max_idx:
        mid_idx = (min_idx+max_idx) // 2
        if t < S[mid_idx]:
            max_idx = mid_idx - 1
        elif t > S[mid_idx]:
            min_idx = mid_idx + 1
        else:
            count += 1
            break
print(count)

Submission status: Accepted

Solution code:
n = int(input())
s = [int(_) for _ in input().split()]
q = int(input())
t = [int(_) for _ in input().split()]
dic = {}
for i in s:
    if i not in dic:
        dic[i] = 1

c = 0
for i in t:
    if i in dic:
        c += 1
print(c)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
C = 0
for i in range(q):
    l = 0
    r = n
    while r - l > 1:
        m = (r + l) // 2
        if T[i] <= S[m]:
            r = m
        else:
            l = m
    if (T[i] == S[l]) or (T[i] == S[r]):
        C += 1
print(C)

Submission status: Accepted

Solution code:

num_s = int(input())

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

num_t = int(input())

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

# Tの要素について、Sに含まれるものを探す

def binary_search(array, x):
    imin = 0
    imax = len(array) - 1
    
    while imin <= imax:
        imid = imin + int((imax - imin) / 2)
        if x > array[imid]:
            imin = imid + 1
        elif x < array[imid]:
            imax = imid - 1
        else:
            return True
    return False

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

print(counter)

Submission status: Accepted

Solution code:
def binarysearch(A,key):
    left=0
    right=n
    while left<right:
        mid=(left+right)//2
        if A[mid]==key:
            return mid
        elif key<A[mid]:
            right=mid
        else:
            left=mid+1
    return None

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

ans=0
for t in T:
    # print(binarysearch(S,t))
    if type(binarysearch(S,t))==int:
        ans+=1
    
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=int(input())
b=list(map(int,input().split()))
ans=0
for x in b:
    l=-1
    r=n
    while r-l>1:
        mid=(l+r)//2
        if a[mid]>=x:
            r=mid
        else:
            l=mid
    lb=r
    l=-1
    r=n
    while r-l>1:
        mid=(l+r)//2
        if a[mid]>x:
            r=mid
        else:
            l=mid
    ub=r
    ans+=ub>lb
print(ans)

Submission status: Accepted

Solution code:
import bisect


def bisect_find(s, i):
    index = bisect.bisect_left(s, i)
    if s[index] == i:
        return True
    return False


input()
s = [int(i) for i in input().split()]
input()
t = [int(i) for i in input().split()]
ans = len([i for i in t if bisect_find(s, i)])
print(ans)

Submission status: Accepted

Solution code:
def binarySearch(A,n,key):
    
    left = 0
    right = n
    while(left < right):
        mid = (left + right)//2
        if(key == A[mid]):
            return 1
        if(key > A[mid]):
            left = mid + 1
        elif(key < A[mid]):
            right = mid
            
    return 0
    
if __name__ == '__main__':
    
    n = int(input())
    L = list(map(int,input().split()))
    q = int(input())
    key = list(map(int,input().split()))
    
    count = 0
    for i in range(q):
        if(binarySearch(L,n,key[i])):
            count += 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 mid
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return None


input()
S = [int(i) for i in input().split()]
input()
T = [int(i) for i in input().split()]
count = 0

for k in T:
    if binarySearch(S, k) is not None:
        count += 1

print(count)

Submission status: Accepted

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

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

cnt = 0

for i in range(q):
    key = T[i]
    cnt += BinarySearch(S,key) 

print(cnt)

Submission status: Accepted

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

def BinarySearch(s,t):
    left = 0
    right = len(s)
    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
count = 0
for i in t:
    count = count + BinarySearch(s,i)
print(count)

Submission status: Accepted

Solution code:
import sys

n = int(input())
s = tuple(map(int, sys.stdin.readline().split()))   # 昇順にソート済み
q = int(input())
t = tuple(map(int, sys.stdin.readline().split()))

result = 0
for x in t:
    first = 0
    last = n - 1
    while first <= last:
        middle = first + (last - first) // 2
        if x == s[middle]:
            result += 1
            break
        elif x < s[middle]:
            last = middle - 1
        else:
            first = middle + 1
print(result)

Submission status: Accepted

Solution code:
"""
二分探索
"""
def BinaraySearch(A, key):
    count = 0
    left = 0
    right = len(A)
    while left < right:
        mid = int((left + right) / 2)
        if A[mid] == key:
            count += 1
            return count
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    else:
        return count

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

ans = 0
for i in range(q):
    ans += BinaraySearch(s, t[i])

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(map(int, input().split()))
s=sorted(set(s))
q=int(input())
t=list(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

count=0
for i in t:
    if binarySearch(s,i):
        count+=1
        #print("a",i)

print(count)

Submission status: Accepted

Solution code:

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

    return False



sum = 0
t = int(input())
A = list(map(int,input().split()))
b = int(input())
C = list(map(int,input().split()))

for res in C:
    if binarySearch(A,res):
        sum += 1

print(sum)

Submission status: Accepted

Solution code:
n = int(input())

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

q = int(input())

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

C = 0

for i in range(q):
  left = 0

  right = n

  while left < right:
    mid = (left + right) // 2
    if S[mid] == T[i]:
      C += 1
      break
    elif T[i] < S[mid]:
      right = mid
    else:
      left = mid + 1

print(C)

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_searach(A, key):   
    left = 0
    right = len(A)
    while(left < right):
        mid = int((left + right) / 2 )
        if A[mid] == key:
            return mid
        elif A[mid] > key:
            right = mid
        else:
            left = mid + 1
    return None

count = 0
for i in T:
    num = binary_searach(S, i)
    if num is not None:
        count += 1
print(count)

Submission status: Accepted

Solution code:
# def linear_search(seq1, seq2):
#     count = 0
#     for i in seq1:
#         for j in seq2:
#             if i == j:
#                 count += 1
#     return count


def binary_search(seq, seq1_len, key):
    left = 0
    right = seq1_len
    center = 0
    while left < right:
        center = (left + right) // 2
        if seq[center] == key:
            return True
        if key < seq[center]:
            right = center
        else:
            left = center + 1
    return False


def main():
    # num_seq1 = int(input())
    seq1_len = int(input())
    seq1 = list(map(int, input().split(" "))) + [0]  # 番兵
    # num_seq2 = int(input())
    input()
    seq2 = list(map(int, input().split(" ")))
    count = 0
    for key in seq2:
        if binary_search(seq1, seq1_len, key):
            count += 1

    print(count)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def bisection(s, tar):
    left = 0
    right = len(s)
    while left + 1 < right:
        middle = (left + right) // 2
        if s[middle] > tar:
            right = middle
        else:
            left = middle
    if s[left] == tar:
        return True
    return False

cnt = 0
for e in t:
    if bisection(s, e):
        cnt += 1
print(cnt)

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
left = 0
right = n
for i in T:
    while(left < right):
        if (i < S[left]) or (i > S[right-1]): break
        mid = int((left+right)/2)
        if S[mid] == i:
            cnt +=1
            break
        elif S[mid] > i: right = mid
        else: left = mid
    left = 0
    right = n

print(cnt)

Submission status: Accepted

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

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

print(C)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(3**12)


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

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

ans = 0
for i in range(num_query):
    tmp = T[i]
    L = 0
    R = len(S)-1
    mid = (L+R)//2

    while L <= R:
        if S[mid] == tmp:
            ans += 1
            break
        elif S[mid] > tmp:
            R = mid-1
        else:
            L = mid+1

        mid = (L+R)//2

print("%d"%(ans))

Submission status: Accepted

Solution code:

def binarySearch(numList, key):
    right = len(A)
    left = 0
    
    while left < right:
        mid = (right + left) // 2
        
        if A[mid] == key:
            return True
        elif A[mid] > key:
            right = mid
        else:
            left = mid + 1
    return False
    
sum = 0
lenA = int(input())
A = list(map(int, input().split())) 
lenB = int(input())
B = list(map(int, input().split())) 
cnt = 0

for i in range(len(B)):
    if binarySearch(A, B[i]):
        cnt += 1
print(cnt)

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 search(key, left, right):
  if right - left <= 1:
    return False

  mid = (left + right) // 2
  if S[mid] == key:
    return True

  if key < S[mid]:
    return search(key, left, mid)
  else:
    return search(key, mid, right)

for t in T:
  if search(t, 0, n):
    count += 1

print(count)

Submission status: Accepted

Solution code:
n=int(input())
s=list(map(int,input().split()))
q=int(input())
cnt=0
t=list(map(int,input().split()))
for i in range(q):
	l=0
	r=n
	while r>l:
		mid=(l+r)//2
		if s[mid]==t[i]:
			cnt+=1
			break
		elif s[mid]>t[i]:
			r=mid
		else:
			l=mid+1
print(cnt)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
S = sorted(map(int, input().split()))
q = int(input())
T = map(int, input().split())
T = set(T)
ans = 0
for t in T:
    i = bisect.bisect_left(S, t)
    if 0 <= i < len(S) and S[i] == t:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def binary_search(num, numlist):
    left = 0
    right = len(numlist)
    while left < right:
        mid = (left + right) // 2
        if numlist[mid] == num:
            return mid
        elif numlist[mid] < num:
            left = mid + 1
        else:
            right = mid
    return -1

if __name__ == '__main__':
    n = input()
    numlist1 = [int(num) for num in input().split()]
    m = input()
    numlist2 = [int(num) for num in input().split()]

    tot = 0
    for num in numlist2:
        if binary_search(num, numlist1) >= 0:
            tot += 1
    print(tot)

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()]

count=0

for i in range(q):
  k=n//2
  if n%2==1:
    l=(n+1)/2
  else:
    l=n/2
  while not((S[k-1] < T[i]) and (S[k] > T[i])):
    if l%2==1:
      l=(l+1)//2
    else:
      l=l//2
    if S[k] > T[i]:
      k= int(k-l)
      if k < 0:
        break
    elif S[k] < T[i]:
      k= int(k+l)
      if k > n-1:
        if S[n-1] == T[i]:
          count+=1
        break
    else:
      count+=1
      break
    #print(S[k])
print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))
ans = 0
for t in T:
    x = bisect_left(S,t)
    if x != len(S):
        if S[x] == t:
            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()))

def bin_search(target, numbers):
    first = 0
    last = len(numbers)
    while first < last:
        mid = (first + last) // 2
        if target < numbers[mid]: last = mid
        elif target > numbers[mid]: first = mid + 1
        else: return mid
    return False

result = 0
for t in T:
    if bin_search(t, S):
        result += 1
        continue
print(result)

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    input()
    s=list(map(int,input().split()))
    input()
    t=list(map(int,input().split()))
    s=set(s)
    t=set(t)
    print(len(s&t))

main()

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = int(input())
    A = set(map(int, input().split()))
    n = int(input())
    cnt = 0
    for b in map(int, input().split()):
        cnt += int(b in A)
    print(cnt)

Submission status: Accepted

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

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

if __name__ == '__main__':
    anw = 0
    for i in T:
        if(binarySearch(S, i)): anw += 1
    print(anw)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))
ans = 0
for t in T:
    if S[bisect.bisect_left(S,t)] == t:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8

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

ans = 0
lenS = len(S)
for i in T:
    idxL = 0
    idxR = lenS
    mch = -1
    while idxL < idxR:
        idxM = (idxL + idxR) // 2
        if S[idxM] == i:
            mch = idxM
            break
        elif S[idxM] < i:
            idxL = idxM + 1
        else:
            idxR = idxM
    if mch >= 0:
        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()))

cnt = 0

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

Submission status: Accepted

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

import bisect
print( sum( s[ bisect.bisect(s,tt)-1 ] ==tt for tt in t) )

Submission status: Accepted

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


def binarysearch( s, e, S, t):
    if s>=e:
        return 0
    elif S[(s+e)//2]==t:
        return 1
    elif S[(s+e)//2]>t:
        return binarysearch( s, (s+e)//2, S, t)
    elif S[(s+e)//2]<t:
        return binarysearch((s+e)//2+1, e, S, t)

    
def main():
    n,S,q,T=inputting()
    count=0
    for t in T:
        flag=binarysearch(0,n,S,t)
        if flag==1:
            count+=1
    print(count)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

def 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:
		temp = bisect.bisect_left(s,i)
		if temp == n:
			continue
		if s[temp] == i:
			ans += 1
	print(ans)

main()

Submission status: Accepted

Solution code:
def BinarySearch(intList, target):
    left = 0
    right = len(intList) - 1
    while left <= right:
        mid = (left + right) // 2
        if intList[mid] == target:
            return True
        elif target < intList[mid]:
            right = mid -1
        elif intList[mid] < target:
            left = mid + 1
    return False


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

for i in range(len(T)):
    if BinarySearch(S, T[i]):
        cnt += 1
print(cnt)

Submission status: Accepted

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

# 二分探索
def binarySearch(A: [int], key: int):
    left = 0
    right = len(A)
    mid = 0
    while left < right:
        mid = (left+right)//2
        if key == A[mid]:
            return 1
        if key > A[mid]:
            left = mid + 1
        elif key < A[mid]:
            right = mid;
    return 0

c = 0
s.sort()
for i in range(len(t)):
    if binarySearch(s, t[i]):
        c += 1
print(c)

Submission status: Accepted

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

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

counter = 0
for t in T:
  counter += bs(t, S, 0, len(S))
print(counter)

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 i in range(q):
    left = 0
    right = n
    mid = (left + right) // 2
    while left < right:
        if t[i] == s[mid]:
            count += 1
            break
        elif t[i] < s[mid]:
            right = mid
            mid = (left + right) // 2
        elif t[i] > s[mid]:
            left = mid + 1
            mid = (left + right) // 2

print(count)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
S = list(map(int,input().split()))
Q = int(input())
T = list(map(int,input().split()))

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return True
    return False

ans = 0
for t in T:
    if index(S,t):
        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()))
c=0
for t in T:
    left=0
    mid=n//2
    right=n
    while left<right:      
        if t == S[mid]:
            c+=1
            break
        elif t > S[mid]:
            left=mid+1
            mid=(right+left)//2
        elif t < S[mid]:
            right=mid
            mid=(right+left)//2
print(c)

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 elT in t:
    minI = 0
    maxI = len(s)-1
    while minI <= maxI:
        middle = (minI+maxI)//2
        if s[middle] == elT:
            count+=1
            break
        elif s[middle] < elT:
            minI = middle+1
        else:
            maxI = middle-1
print(count)

Submission status: Accepted

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

    while left < right:  # 見つからなければ最後にleft == rightになる。
        mid = (left + right) // 2
        if A[mid] == key:
            return mid
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1

    return None


import sys
input = sys.stdin.readline

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

count = 0

for t in T:
    match = binary_search(S, t)
    if match is not None:
        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()))
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
len_a = input()
a = set(map(int, input().split()))
len_b = input()
b = set(map(int, input().split()))

print(len(a & b))

Submission status: Accepted

Solution code:
def binary_search(A, key, n):
    left = 0
    right = n
    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

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

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

print(counter)

Submission status: Accepted

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

n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]
ans = 0
for i in range(q):
    if bs(s,t[i]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=[]
A=input().split()
A=[int(u) for u in A]
q=int(input())
B=[]
B=input().split()
B=[int(u) for u in B]
count=0
for j in range(0,q):
    right=n-1
    left=0
    while 1:
        k=int((right+left)/2)
        if A[k]>B[j]:
            right=int(k)
        elif A[int(k)]==B[j]:
            count=count+1
            right=n-1
            left=0
            break
        else:
            left=int(k)
        if right-left==1 or left-right==1:
            if A[right]==B[j] or A[left]==B[j]:
                count=count+1
                right=n-1
                left=0
                break
            else :
                right=n-1
                left=0
                break
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Oct 24 00:11:24 2019

@author: iwao_yuuki
"""

import math

n = int(input(""))
S = [int(x) for x in input().split()]

q = int(input(""))
T = [int(x) for x in input().split()]

cnt = 0
for i in T:
    head = 0
    tail = n-1

    while head <= tail:
        center = math.floor((head+tail)/2)

        if S[center] == i:
            cnt += 1
            break
        else:
            if S[center] < i:
                head = center + 1
            else:
                if S[center] > i:
                    tail = center - 1

print(cnt)

Submission status: Accepted

Solution code:

n=int(input())

s=[int(x) for x in input().split()]

q=int(input())

t=[int(y) for y in input().split()]



cou=0

for i in range(q):
    left=0
    right=n
    key=t[i]
    while left<right:
        cen=(left+right)//2
        if s[cen]==key:
            cou+=1
            break
        elif s[cen]>key:
            right=cen
        else:
            left=cen+1

print(cou)

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()]

ans=0
for i in t:
    l,r=0,n
    while l<=r:
        m=(l+r)//2
        if s[m]==i:
            ans+=1
            break
        elif s[m]>i:
            r=m-1
        else:
            l=m+1
print(ans)

Submission status: Accepted

Solution code:
S=[]
T=[]

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

def B(S,n,t):
    low=0
    high=n-1

    while low <= high:

        mid =(low + high)//2
        guess = S[mid]

        if guess == t:
           return 1;

        if guess > t:
            high = mid-1
        else:
            low = mid + 1
    return 0

c=0

for i in range(q):
    if(B(S,n,T[i])):
        c=c+1
print(c)

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 range(q):
    a=t[i]
    
    left=0
    right=n-1
    
    while left<=right: 
        center=(left+right)//2
        m=s[center]
       
        if m==a:
            cnt+=1
            break
            
        elif m > a:
            right=center-1
        elif m < a:
            left=center+1

print(cnt)

Submission status: Accepted

Solution code:


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

n = int(input())
l1 = [int(x) for x in input().split()] 
m = int(input())
l2 = [int(x) for x in input().split()] 

cnt = 0
left = 0
right = n

for key in l2: 
    if(binarySearch(left, right, l1, key) == True):
        cnt = cnt + 1

print(cnt)

Submission status: Accepted

Solution code:
def search(arr, target):
    l, r = 0, len(arr) - 1
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] > target:
            r = mid - 1
        else:
            l = mid + 1
    return False


if __name__ == '__main__':
    n = int(input())
    arr_1 = list(map(int, input().split()))
    q = int(input())
    arr_2 = list(map(int, input().split()))
    ans = 0
    for element in arr_2:
        if search(arr_1, element):
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=int(input())
b=list(map(int,input().split()))

a.sort()
b.sort()
c=0
for i in b:
    right=n
    left=0
    while left<right:
        mid=(left+right)//2
        if a[mid]==i:
            c=c+1
            break
        elif i<a[mid]:
            right=mid
        else:
            left=mid+1
        
print(c)

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
S.sort()
for i in range(q):
    l = 0
    r = n-1
    ans = T[i]
    while l <= r:
        c = int((l+r)/2) #center
        if S[c] == ans:
            cnt += 1
        if S[c] < ans:
            l = c+1
        elif S[c] > ans:
            r = c-1
        else:
            break
        
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))
a = 0
for ti in t:
  # ti in s ?
  low = 0
  high = n - 1
  while low <= high:
    mid = (low + high) // 2
    if s[mid] > ti:
      high = mid - 1
    elif s[mid] < ti:
      low = mid + 1
    else:
      a += 1
      break
print(a)

Submission status: Accepted

Solution code:
n=int(input()) 
s=input().split() 

q=int(input()) 
t=input().split() 

s=set(s)
t=set(t)

print(len(s&t))

Submission status: Accepted

Solution code:
num1 = int(input())
arr1 = list(map(int,input().split()))

num2 = int(input())
arr2 = list(map(int,input().split()))

count = 0

for i in range(num2):
    left = 0
    right = num1
    
    while left < right:
        mid = int((left + right) /2)
        
        if arr1[mid] == arr2[i]:
            count +=1
            break
        
        elif arr2[i] < arr1[mid]:
            right = mid
        else:
            left = mid +1
        

print(count)