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:
# -*- coding: utf-8 -*-


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 "NOT_FOUND"


if __name__ == '__main__':

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

    count = 0
    for t in T:
        if binarySearch(S, t) != "NOT_FOUND":
            count += 1

    print(count)

Submission status: Accepted

Solution code:
first_set_count = int(input());
first_set = [int(n) for n in input().split()];
second_set_count = int(input());
second_set = [int(n) for n in input().split()];

def binary_search(num, s, start, end):
    while start < end:
        mid = (end + start) // 2;
        if num == s[mid]:
            return True;
        elif num > s[mid]:
            start = mid + 1;
        else:
            end = mid;
    return False;

count = 0;
for num in second_set:
    if binary_search(num, first_set, 0, len(first_set)):
        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 True
        elif key < S[mid]:
            right = mid
        else:
            left = mid + 1

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

#%%
sum = 0

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

Submission status: Accepted

Solution code:
def bin_search(m, s, left, right):
    if left <= right:
        n = (left + right) // 2
        if s[n] == m:
            return True
        elif m < s[n]:
            return bin_search(m, s, left, n-1)
        else:
            return bin_search(m, s, n+1, right)


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

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

count = 0
for i in t:
    if bin_search(i, s, 0, len(s)-1):
        count += 1

print(count)

Submission status: Accepted

Solution code:
import array

def main():
    n1 = int(input())
    li1 = array.array('l', [int(x) for x in input().split()])
    n2 = int(input())
    li2 = array.array('l', [int(x) for x in input().split()])
    count = 0

    for l in li2:
        if binary_search(li1, l):
            count += 1

    print(count)


def binary_search(li, x):
    if len(li) == 0:
        return False
    
    mid = len(li)//2
    
    k = li[mid]
    if k == x:
        return True
    elif k > x:
        li = li[:mid]
    else:
        li = li[mid+1:]
        
    return binary_search(li, x)

if __name__=='__main__':
    main()

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 'Not_found'

if __name__ == '__main__':
    c = 0
    n = int(input())
    hoge1 = [int(x) for x in input().split()]
    q = int(input())
    for key in (int(x) for x in input().split()):
        if binarySearch(hoge1, key) == 'Not_found':
            continue
        else:
            c += 1
    print (c)

Submission status: Accepted

Solution code:
def search(L,e):
    """Lは昇順"""
    def bsearch(L,e,low,high):
        if high == low:
            return L[low] == e
        mid = (low + high)//2
        if L[mid] == e:
            return True
        elif L[mid] > e:
            if low==mid:
                return False
            else:
                return bsearch(L,e,low,mid-1)
        else:
            return bsearch(L,e,mid+1,high)
    if len(L) == 0:
        return False
    else:
        return bsearch(L,e,0,len(L)-1)
        
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 t:
    if search(s,i):
        count+=1

print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
s=sys.stdin.readlines()
print(len(set(s[1].split())&set(s[3].split())))

Submission status: Accepted

Solution code:
def binarySearch(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

n = int(input())
A = list(map(int,input().split()))
input()
print(sum(binarySearch(e) for e in map(int,input().split())))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = list(map(int, input().split()))
input()
k = 0
for e in map(int, input().split()):
    i = bisect.bisect_left(A, e)
    if i < n and A[i] == e: k += 1 
print(k)

Submission status: Accepted

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

def search(a, v):
  l = 0
  r = len(a)
  while l + 1 < r:
    i = int((l + r) / 2)
    if a[i] <= v:
      l = i
    else:
      r = i
  return a[l] == v

print(sum(list(map(lambda e: search(S, e), T))))

Submission status: Accepted

Solution code:
import sys
data = []
for line in sys.stdin:
	data.append(line.split())

S = []
T = []
ans = []
S = data[1]
T = data[3]

count = 0
for t in T:
    l = 0
    r = len(S)

    while l < r :
        i = (l + r) / 2
        if int(S[i]) < int(t) :
            l = i + 1
        elif int(S[i]) > int(t) :
            r = i
        else :
            count = count + 1
            break

print(count)

Submission status: Accepted

Solution code:
#coding: UTF-8
#@document_it

def document_it(func):
  def new_function(*args,**kwargs):
    print('Running function:', func.__name__)
    print('Positional arguments:', args)
    print('Kewword arguments:', kwargs)
    result = func(*args,**kwargs)
    print('Result:', result)
    return result
  return new_function

#@document_it
def bsearch(v,list,l=None):
  if l == 0 or list == []:
    return False
  if l==None:
    l = len(list)
  
  import math
  T = math.ceil(math.log2(l))
  t = 0
  wid = l
  offset = 0
  while t <= T:
    if wid == 0:
        return False
    pos = wid//2 + offset
    w = list[pos]
    if wid == 1:
        if v == w:
            return True
        else:
            return False
    else:
        if v == w:
            return True
        elif v < w:
            wid = wid//2
        else:
            wid = wid//2 - 1 + wid%2
            offset = pos + 1
    t+=1



def exe():
    n = int(input())
    S = list(map(int,input().split()))
    q = int(input())
    T = map(int,input().split())
    ans = 0

    for t in T:
        if bsearch(t,S,n):
            ans += 1

    print(ans)

if __name__ == '__main__':
    exe()

Submission status: Accepted

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

import sys

def bsearch(val, _list):
    i_min = 0
    i_max = len(_list) - 1
    while True:
        i_mid = (i_min + i_max) // 2  # i_min + (i_max-i_min) // 2, if integer overflow can occur
        m_val = _list[i_mid]
        # print(val, m_val, i_mid, i_min, i_max)
        if val == m_val:
            return True
        elif val < m_val:
            i_max = i_mid - 1
            if i_max < i_min:
                return False
        else:
            i_min = i_mid + 1
            if i_min > i_max:
                return False

n = int(sys.stdin.readline())
s = list(map(int, sys.stdin.readline().split()))
q = int(sys.stdin.readline())
t = list(map(int, sys.stdin.readline().split()))

total = 0

for x in t:
    if bsearch(x, s):
        total += 1

print(total)

Submission status: Accepted

Solution code:
import sys

if __name__ == '__main__':
    data = []
    count = 0
    for line in sys.stdin:
        data.append(line.split())
    s = list(map(int, data[1]))
    n = int(data[0][0])
    q = int(data[2][0])
    t = list(map(int, data[3]))
    for i in range(0, q):
        head = 0
        tail = n - 1
        while True:
            if head > tail :
                break
            center = (head + tail)//2
            if s[center] == t[i] :
                count = count + 1
                break
            elif s[center] < t[i]:
                head = center + 1
            else :
                tail = center - 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

for i in range(q):
    left = 0
    right = n
    while left < right:
        mid = (right + left) // 2
        if t[i] == s[mid]:
            count += 1
            break
        elif t[i] < s[mid]:
            right = mid
        elif t[i] > s[mid]:
            left = mid+1
print(count)

Submission status: Accepted

Solution code:
def m():
 input();s=set(input().split())
 input();print(len(s&set(input().split())))
if'__main__'==__name__:m()

Submission status: Accepted

Solution code:
n =int(input())

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

q = int(input())

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

def BinSearch(S, t):
    l = len(S)
    s = S
    n1 = 0
    n2 = l
    while (n2 - n1) > 4:
        x = (n2 + n1) // 2
        if S[x] == t:
            return True
        elif S[x] < t:
            n1 = x
        else:
            n2 = x
    return t in S[n1:n2]

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

Submission status: Accepted

Solution code:
def binary_search(ary, key, imin, imax):
    if imax < imin:
        return False
    else:
        imid = imin + (imax - imin) // 2
        if ary[imid] > key:
            return binary_search(ary, key, imin, imid - 1)
        elif ary[imid] < key:
            return binary_search(ary, key, imid + 1, imax)
        else:
            return True

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

cnt = 0
for i in t:
    if binary_search(s, i, 0, n-1):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import re

question1 =int(input())
question2 =input()
question3 =int(input())
question5 =input()


S = re.split(r' ',question2)
S=list(map(int, S))

T = re.split(r' ',question5)
T=list(map(int, T))

if (question1==0) or (question3==0):
    print(0)
else:
    S = set(S)
    T = set(T)
    matched_list = list(S & T)
    print(len(matched_list))

Submission status: Accepted

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

Sset = set(S)
Tset = set(T)

print(len(Sset & Tset))

Submission status: Accepted

Solution code:
N = int(input())
S = list(set(map(int, input().split())))
S.sort()
Q = int(input())
T = list(map(int, input().split()))
ans = 0
for i in range(Q):
    OK = 0
    NG = len(S)
    while abs(OK-NG)>1:
        mid = (OK+NG)//2
        if S[mid]<=T[i]:
            OK = mid
        else:
            NG = mid
    if S[OK] == T[i]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
def binSearch(x,data):
    start = 0
    end = len(data)
    while start <= end:
        mid = int((start + end) / 2)
        if data[mid] == x:
            return 1
        elif int(data[mid]) > int(x):
            end = mid - 1
        else:
            start = mid + 1
    return 0
l = []
for i in sys.stdin:
    l.append(i)
l[1] = l[1].split()
l[3] = l[3].split()
count = 0
for i in range(0,len(l[3])):
    count += binSearch(l[3][i],l[1])
print(count)

Submission status: Accepted

Solution code:
ns = int(input())
s = list(map(int, input().split()))
nt = int(input())
t = list(map(int, input().split()))

count = 0

for i in t:
    left = 0
    right = ns
    while left < right:
        mid = int((left + right) / 2)
        if s[mid] == i:
            count += 1
            break
        elif i < s[mid]:
            right = mid
        else:
            left = mid + 1

print(count)

Submission status: Accepted

Solution code:
def count(xs, ys):
    """Returns a count of elements in ys which is also in xs.
    - xs: a sequence of integers sorted in ascending order.
    - ys: a sequence of different integers.

    >>> count([1, 2, 3], [1, 3])
    2
    >>> count([1, 2, 3, 4, 5], [3, 4, 1])
    3
    >>> count([1, 2, 3], [5])
    0
    >>> count([1, 1, 2, 2, 3], [1, 2])
    2
    """
    def binsearch(i, j, n):
        while i <= j:
            mid = (i + j) // 2
            if xs[mid] > n:
                j = mid - 1
            elif xs[mid] < n:
                i = mid + 1
            else:
                return True

        return False

    return [binsearch(0, len(xs)-1, y) for y in ys].count(True)

def run():
    _ = input()  # flake8: noqa
    s = [int(i) for i in input().split()]
    _ = input()  # flake8: noqa
    t = [int(j) for j in input().split()]

    print(count(s, t))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
def binarySearch(array, key):
    left = 0
    right = len(array)
    while left < right:
        mid = int((left + right) / 2)
        if key == array[mid]:
            return True
        elif key > array[mid]:
            left = mid + 1
        elif key < array[mid]:
            right = mid
        else:
            print("ERROR")
    return False


n = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]
a = [x for x in t if binarySearch(s, x)]
print(len(a))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
s = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
c = 0
for i in t:
    j = bisect.bisect_left(s, i)
    if j < n and s[j] == i:
        c += 1
print(c)

Submission status: Accepted

Solution code:
def binary_search(S, key):
    S_len = len(S)

    if S_len == 0:
        return -1

    mid = S_len // 2

    if S[mid] == key:
        return 1

    if S[mid] >= key:
        return binary_search(S[:mid], key)
    else:
        return binary_search(S[mid + 1:], key)

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

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

result = 0

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

        if S[mid] > t:
            right = mid
        else:
            left = mid + 1

print(result)

Submission status: Accepted

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

s_set = set(s)
t_set = set(t)
sandt = s_set & t_set
print(len(sandt))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 30 11:33:59 2018
ALDS1-4a_r  バイナリサーチ

@author: maezawa
"""

def binary_search(a, key):
    n = len(a)
    left = 0
    right = n
    while left < right:
        #print(left, right)
        mid = (right+left)//2
        if a[mid] == key:
            return mid
        elif a[mid] > key:
            right = mid
        else:
            left = mid + 1
    return n

n = int(input())
s = list(map(int, input().split())) # in演算子を使うためにはsはlistである必要がある。
q = int(input())
t = map(int, input().split())

cnt = 0
for i in t:
    if binary_search(s, i) < n:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
#! python3
# binary_search.py

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

def binary_search(t):
    global S
    min_i, max_i = 0, len(S)-1
    i = int((min_i + max_i)/2)
    while min_i <= max_i:
        if t == S[i]:
            return i
            break
        elif t < S[i]:
            max_i = i - 1
        else:
            min_i = i + 1
        i = int((min_i + max_i)/2)
    return None

c = 0
for t in T:
    if binary_search(t) != None:
        c += 1
print(c)

Submission status: Accepted

Solution code:
n = int(input())
a = set(input().split())
m = int(input())
b = set(input().split())
print(len(a&b))

Submission status: Accepted

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

S_s =set(S)
T_s =set(T)
C = S_s & T_s
print(len(C))

Submission status: Accepted

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

for i in t:
    l = 0
    r = n-1
    cen = int((l+r) / 2)
    while r >= l :
#        print("0:",i,l,r,cen,s[cen])
        if i > s[cen]:
            l = cen
            cen = int((l+r) / 2)
#            print("1:",l,r,cen,s[cen])
        elif i < s[cen]:
            r = cen
            cen = int((l+r) / 2)
#            print("2:",l,r,cen,s[cen])
        if i == s[cen] or i == s[l] or i == s[r]:
            c += 1
#            print("!")
            break
        if l+1 > r-1:
#            print("!!",i)
            break
print(c)

Submission status: Accepted

Solution code:
def BinarySearch(n,key,A):
    left=0
    right=n
    while left<right:
        mid=(int)((left+right)/2)
        if A[mid]==key:
            return 2
        if key<A[mid]:
            right=mid
        if key>A[mid]:
            left=mid+1
    return 1
cnt=0
n=int(input())
S=[0 for i in range(n)]
S=input().split()
for i in range(n):
    S[i]=(int)(S[i])
q=int(input())
T=[0 for i in range(q)]
T=input().split()
for i in range(q):
    T[i]=(int)(T[i])
    a=BinarySearch(n,T[i],S)
    if a==2:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:

sn = int(input())
S = [0 for i in range(sn)]
S = input().split()
for i in range(sn):
	S[i] = int(S[i])

tn = int(input())
T = [0 for i in range(tn)]
T = input().split()
for i in range(tn):
	T[i] = int(T[i])


cnt=0

for i in range(tn):

	key=T[i]
	left=0
	right=sn
	c=0

	while left<right:

		mid=(int)((left+right)/2)

		if S[mid]==key:
			if c==0:
				cnt+=1
				c=1
				
			break

		if S[mid]>key:
			right=mid

		if S[mid]<key:
			left=mid+1


print(cnt)

Submission status: Accepted

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

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

for i in T:
    left = 0
    right = len(S)-1
    center = int( (left+right) / 2 )

    while center >= left and center <= right:
        if S[center] == i:
            cnt += 1
            break
        elif S[center] > i:
            right = center-1
            center = int( (left+right) / 2 )
        elif S[center] < i:
            left = center+1
            center = int( (left+right) / 2 )

print(cnt)

Submission status: Accepted

Solution code:
#coding: Shift_JIS

def set_array(a,n):
	str=input()
	array=str.split()
	for i in range(n):
		a.append(int(array[i]))
	

n=int(input())
S=[]
set_array(S,n)
q=int(input())
T=[]
set_array(T,q)
C=0

def binary_search(S,x):
	s=0
	e=len(S)-1
	while s<=e:
		med=int((s+e)/2)
		if S[med]==x: return 1
		elif S[med]>x: e=med-1
		else: s=med+1
	return 0

for v in T:
	C+=binary_search(S,v)

print(C)

Submission status: Accepted

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

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


s.sort()

cnt=0
for i in range(q):
    x=binarySearch(s,t[i])
    if x!=(-1):
        cnt+=1

print(cnt)

Submission status: Accepted

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

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

    return None


def main():
    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):
        if binary_search(s, t[i]) is not None:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

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 bs(l,key):
    left=0
    right=len(l)
    
    while left<right:
        mid=int((left+right)/2)

        if l[mid]==key:

            return  True
        elif key<l[mid]:
            right=mid
        else:
            left=mid+1
    
    return False
            


n1=int(input())
l1=list(map(int,input().split()))

n2=int(input())
l2=list(map(int,input().split()))

cnt=0

for x in l2:
    if bs(l1,x):
        cnt+=1

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

S=list(map(int,S))
T=list(map(int,T))

cnt=0

for i in range(q):
	left=0
	right=n-1
	while left<=right:
		mid=int((left+right)/2)
		if S[left]>T[i] and S[right]<T[i]:
			break
		if S[mid]==T[i]:
			cnt+=1
			break
		elif S[mid]>T[i]:
			right=mid-1
		elif S[mid]<T[i]:
			left=mid+1

print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
S=input().split()
q=int(input())
T=input().split()
cnt=0
for i in range(len(T)):
    T[i]=int(T[i])
for i in range(len(S)):
    S[i]=int(S[i])
for i in range(len(T)):
    c=0
    left=0
    right=n
    while left<right and c==0:
        mid=(left+right)/2
        mid=int(mid)
        if S[mid]==T[i]:
            cnt+=1
            c+=1
        elif T[i]<S[mid]:
            right=mid
        else:
            left=mid+1
print(cnt)

Submission status: Accepted

Solution code:
#16D8102008K 4-B Yagyu Hauzki

n=int(input())
s=set(map(int,input().split()))
q=int(input())
t=set(map(int,input().split()))
print(len(t&s))

Submission status: Accepted

Solution code:
#16D8101014F 久留米 竜之介 2018/5/14
n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))
point=0
for i in T:
	left=0
	right=n
	while left < right:
		mid=int((left+right)/2)
		if S[mid] == i:
			point += 1
			break
		elif i < S[mid]:
			right = mid
		else:
			left = mid + 1
	#print(i,point)

print(point)

Submission status: Accepted

Solution code:
n=input()
A=set(input().split())
m=input()
B=set(input().split())
print(len(A&B))

Submission status: Accepted

Solution code:
############################
# 再帰的に呼出す関数
def half(a,b,low,high): #aは配列,bはソートされてない要素,cはcenter

    if(low > high):
        return 0

    c = int((low+high)/2)

    if(a[c] == b):
        return 1
    elif(a[c] < b):
        return half(a,b,c+1,high)
    elif(a[c] > b):
        return half(a,b,low,c-1)
    else:
        return 1
#############################


n = int(input())
s = list(map(int,input().split()))
q = int(input())
r = list(map(int,input().split()))
cou = 0

for i in range(q):
    cou += half(s,r[i],0,len(s))

print(cou)

Submission status: Accepted

Solution code:
############################
# 再帰的に呼出す関数
def half(a,b,low,high):

    if(low > high):
        return 0

    c = int((low+high)/2)

    if(a[c] == b):
        return 1
    elif(a[c] < b):
        return half(a,b,c+1,high)
    elif(a[c] > b):
        return half(a,b,low,c-1)
#############################


n = int(input())
s = list(map(int,input().split()))
q = int(input())
r = list(map(int,input().split()))
cou = 0

for i in range(q):
    cou += half(s,r[i],0,n-1)

print(cou)

Submission status: Accepted

Solution code:
c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
s.sort()

print(len(set(s)&set(t)))

Submission status: Accepted

Solution code:
n_num = int(input())
n_list = list(map(int, input().split()))
q_num = int(input())
q_list = list(map(int, input().split()))

count = 0
for q in q_list:
	lower = 0
	higher = len(n_list) - 1
	m = (higher - lower) // 2

	while lower <= higher:
		if n_list[m] == q:
			count += 1
			break
		elif n_list[m] > q:
			higher = m - 1
			m = lower + (higher - lower) // 2
		else:
			lower = m + 1
			m = lower + (higher - lower) // 2

print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def binarySearch(array, key):
    left = 0
    right = len(array)
    while left < right:
        mid = int((left + right) / 2)
        if key == array[mid]:
            return True
        elif key > array[mid]:
            left = mid + 1
        elif key < array[mid]:
            right = mid
        else:
            print("ERROR")
    return False
 
 
n = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]
a = [x for x in t if binarySearch(s, x)]
print(len(a))

Submission status: Accepted

Solution code:
input()
s = set(n for n in input().split())
input()
t = set(n for n in input().split())
print(len(s & t))

Submission status: Accepted

Solution code:

def bs(A, n):
    l=0
    r=len(A)
    while l<r:
        mid=int((l+r)/2)
        if A[mid]==n:
            return mid
        else:
            if n<A[mid]:
                r=mid
            else:
                l=mid+1

    return -1

S=int(input())
A=[int(i) for i in input().split()]

T=int(input())
B=[int(j) for j in input().split()]

A.sort()

cnt=0
for i in range(T):
    x=bs(A,B[i])
    if x!=(-1):
        cnt=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(list, key):
    left = 0
    right = len(list)

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

    return False

ans = 0
for t in T:
    if binarySearch(S, t) == True:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def binary_search(l, t):
    left = 0
    right = len(l) - 1

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

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

    cnt = 0
    for et in t:
        bl = binary_search(s, et)
        if bl:
            cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def binary_search(l, t):
    left = 0
    right = len(l)

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

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

    cnt = 0
    for et in t:
        bl = binary_search(s, et)
        if bl:
            cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n = int(input())
S = list(map(int, input().split(' ')))
q = int(input())
T = list(map(int, input().split(' ')))
counter = 0
def binary_search(A, left, right, t):
    if(left > right):
        return
    global counter
    center = (right + left) // 2
    if(A[center] == t):
        counter += 1
        return
    elif(A[center] < t):
        binary_search(A, center+1, right, t)
    else:
        binary_search(A, left, center-1, t)

for t in T:
    binary_search(S, 0, n, t)
print(counter)

Submission status: Accepted

Solution code:
# def binary_search_original(ary, target):

#     if ary:
#         ind = len(ary) // 2
#         if target == ary[ind]:
#             return True
#         elif target < ary[ind]:
#             return binary_search(ary[:ind], target)
#         else:
#             return binary_search(ary[ind + 1:], target)

#     else:
#         return False


def binary_search(ary, target):

    left = 0
    right = len(ary)

    while left < right:
        mid = (left + right) // 2

        if ary[mid] == target:
            return True
        elif ary[mid] < target:
            left = mid + 1
        else:
            right = mid

    return False


if __name__ == '__main__':

    n = int(input())
    S = [int(_) for _ in input().split()]
    q = int(input())
    T = [int(_) for _ in input().split()]
    cnt = 0

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

    print(cnt)

Submission status: Accepted

Solution code:
# ALDS1_4_B.
# バイナリサーチ。

def intinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def binary_search(S, k):
    a = 0; b = len(S) - 1
    if b == 0: return S[0] == k
    while b - a > 1:
        c = (a + b) // 2
        if k <= S[c]: b = c
        else: a = c
    return S[a] == k or S[b] == k
    
def main():
    n = int(input())
    S = intinput()
    q = int(input())
    T = intinput()
    count = 0
    for k in T:
        if binary_search(S, k): count += 1
    print(count)

    
if __name__ == "__main__":
    main()

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

def binary_search(imin, imax, target):
    n = int(imax - imin + 1)
    if n == 1:
        if S[imin] == target:
            return 1
        else:
            return 0
            
        
    if n % 2 == 0:
        c = int(imin + n/2)
        if target >= S[c]:
            imin = c
            return binary_search(imin, imax, target)

        else:
            imax = c-1
            return binary_search(imin, imax, target)



    else:
        n = (n-1)/2
        c = int(imin + n)
        if target >= S[c]:
            imin = c
            return binary_search(imin, imax, target)

        else:
            imax = c-1
            return binary_search(imin, imax, target)


        

def judge(array, target, imin, imax,c):
    if target >= array[c]:
        imin = c
        return binary_search(imin, imax, target)

    else:
        imax = c-1
        return binary_search(imin, imax, target)



cnt = 0
for target in T:
    cnt += binary_search(0, n-1, target)

print(cnt)