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:
def solve(s_list, t_list):
    ans = 0
    s_length = len(s_list)
    for t in t_list:
        left, right = 0, s_length
        if binary_search(s_list, left, right, t):
            ans += 1
    return ans


def binary_search(s_list, left, right, t):
    # [left, right)
    if right > left:
        mid = (left + right) // 2
        if s_list[mid] == t:
            return True
        elif s_list[mid] > t:
            right = mid
        else:
            left = mid + 1
        return binary_search(s_list, left, right, t)
    return False


def main():
    n = int(input())
    s_list = list(map(int, input().split()))
    q = int(input())
    t_list = list(map(int, input().split()))

    ans = solve(s_list, t_list)
    print(ans)


main()

Submission status: Accepted

Solution code:
def search(l, n):
    l = l.copy()
    l.append(n)
    i = 0
    while l[i] != n:
        i += 1

    if i == len(l) - 1:
        print("NOT FOUND")
    else:
        print("FOUND")


n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]

s = set(s)
ans = 0
for ti in t:
    if ti in s:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def search(l, n):
    left = 0
    right = len(l) - 1
    m = (left + right) // 2

    while right - left > 1:
        if n == l[m]:
            return True
        elif n < l[m]:
            right = m
        elif n > l[m]:
            left = m
        else:
            raise Exception()

        m = (left + right) // 2

    if l[left] == n or l[right] == n:
        return True
    else:
        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 ti in t:
    if search(s, ti):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def search(l, n):
    left = 0
    right = len(l)
    m = (left + right) // 2

    # while right - left > 1:
    while left < right:
        if n == l[m]:
            return True
        elif n < l[m]:
            right = m
        elif n > l[m]:
            left = m + 1
        else:
            raise Exception()

        m = (left + right) // 2


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 ti in t:
    if search(s, ti):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def search(l, n):
    left = 0
    right = len(l) - 1
    while right - left > 1:
        m = (left + right) // 2
        if n == l[m]:
            return True
        elif n < l[m]:
            right = m
        else:
            left = m

    # print(left, right)
    if l[left] == n or l[right] == n:
        return True
    else:
        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 ti in t:
    if search(s, ti):
        ans += 1

print(ans)

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())
l1=sorted(list(map(int,input().split())))
m=int(input())
l2=sorted(list(map(int,input().split())))
def nibutan(a,k):
    l=0
    r=len(a)
    while r>l:
        m=(r+l)//2
        if a[m]==k:
            return m
        elif k<a[m]:
            r=m
        else:
            l=m+1
    return -1
c=0
for i in l2:
    if nibutan(l1,i)!=-1:
        c+=1
print(c)

Submission status: Accepted

Solution code:
from bisect import bisect_left

def index(A, x):
	i = bisect_left(A, x)
	if i != len(A) and A[i] == x:
		return i
	else:
		return -1


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

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

print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf 8 -*-
# Binary Search
# 2019. 4/30

global A
global n

def binarySearch(key):
    left = 0
    right = n
    key = int(key)

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

if __name__ == '__main__':
    sum = 0
    n = int(input())
    A = list(map(int, input().split()))

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

    for i in range(q):
        if binarySearch(B[i]) == 1:
            sum = sum + 1

    print("{}".format(sum))

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

def biSearch(A, key):
  left = 0
  right = n
  while left < right:
    mid = int((left + right) / 2)
    if A[mid] == key:
      return 1
    if A[mid] > key:
      right = mid
    if A[mid] < key:
      left = mid + 1
  return 0
for t in T:
  ans += biSearch(S, t)
print(ans)

Submission status: Accepted

Solution code:
class BinarySearch:

    def __init__(self, S, n):
        self.target = S
        self.length = n
    
    def search(self, key):
        left = 0
        right = self.length
        while left<right:
            mid = int((left+right)/2)
            if self.target[mid]==key:
                return True
            elif self.target[mid]<key:
                left = mid + 1
            elif self.target[mid]>key:
                right = mid
        return False


def main():
    n = int(input())
    S = [int(i) for i in input().split()]
    q = int(input())
    T = (int(i) for i in input().split())
    bs = BinarySearch(S, n)
    count = 0
    for t in T:
        if bs.search(t):
            count += 1
    print(count)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def binaryArraySearch(ordered, t):
  low = 0
  high = len(ordered) - 1

  while low <= high:
    mid = (low + high) // 2
    if t == ordered[mid]:
      return True
    elif t < ordered[mid]:
      high = mid - 1
    else:
      low = mid + 1
  return False


n = int(input())
S = [int(x) for x in input().split()] # 昇順に整列されている
q = int(input())
T = [int(x) for x in input().split()]

count = 0
for target in T:
  if binaryArraySearch(S, target):
    count += 1

print(count)

Submission status: Accepted

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

Submission status: Accepted

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


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

q = int(raw_input())
T = []
T = map(int, raw_input().split())
count = 0
for key in T:
	if binarySearch(S, key):
		count += 1
print count

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def BinarySearch(A, n, key):
    #left:left end index                                      
    #right:right end index + 1                                
    left = 0
    right = n

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

    return "NOT_FOUND"


if __name__ == "__main__":
    n1 = int(raw_input())
    x1 = map(int, raw_input().split())
    n2 = int(raw_input())
    x2 = map(int, raw_input().split())

    C_num = 0

    for i in range(n2):
	if BinarySearch(x1, n1, x2[i]) != "NOT_FOUND":
            C_num += 1

    print(C_num)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B
# Binary Search
# Result:
import sys

NO_ANSWER = -1

def binary_sarch(target, ary, start, end):
    if start == end:
        if target == ary[start]:
            return start
        else:
            return NO_ANSWER

    mid = (start + end) / 2
    if target < ary[mid]:
        return binary_sarch(target, ary, start, mid)
    elif target > ary[mid]:
        return binary_sarch(target, ary, mid + 1, end)
    else: # target == ary[mid]
        return mid


### main
ary_s_len = int(sys.stdin.readline().rstrip())
ary_s = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
ary_t_len = int(sys.stdin.readline().rstrip())
ary_t = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
assert len(ary_s) == ary_s_len
assert len(ary_t) == ary_t_len

count = 0
for e in ary_t:
    idx = binary_sarch(e, ary_s, 0, ary_s_len - 1)
    if idx >= 0:
        count += 1
print count

Submission status: Accepted

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

cnt = 0
cnt = 0
for ti in t:
	low = 0
	high = n - 1
	while low <= high:
		m = ( low+high )/2
		if ti < s[m]:
			high = m - 1
		elif s[m] < ti:
			low = m + 1
		else:
			cnt += 1
			break

print( cnt )

Submission status: Accepted

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

cnt = 0
cnt = 0
for ti in t:
	low = 0
	high = n - 1
	while low <= high:
		m = ( low+high )//2
		if ti < s[m]:
			high = m - 1
		elif s[m] < ti:
			low = m + 1
		else:
			cnt += 1
			break

print( cnt )

Submission status: Accepted

Solution code:
n = int( raw_input( ) )
s = [ int( val ) for val in raw_input( ).split( " " ) ]
q = int( raw_input( ) )
t = [ int( val ) for val in raw_input( ).split( " " ) ]

cnt = 0
cnt = 0
for ti in t:
	low = 0
	high = n - 1
	while low <= high:
		m = ( low+high )//2
		if ti < s[m]:
			high = m - 1
		elif s[m] < ti:
			low = m + 1
		else:
			cnt += 1
			break

print( cnt )

Submission status: Accepted

Solution code:
n = int( raw_input( ) )
s = [ int( val ) for val in raw_input( ).split( " " ) ]
q = int( raw_input( ) )
t = [ int( val ) for val in raw_input( ).split( " " ) ]
t.sort( )

cnt = 0
for ti in t:
	low = 0
	high = n - 1
	while low <= high:
		m = ( low+high )//2
		if ti < s[m]:
			high = m - 1
		elif s[m] < ti:
			low = m + 1
		else:
			cnt += 1
			break

print( cnt )

Submission status: Accepted

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

cnt = 0
for ti in t:
	low = 0
	high = n - 1
	while low <= high:
		m = ( low+high )//2
		if ti < s[m]:
			high = m - 1
		elif s[m] < ti:
			low = m + 1
		else:
			cnt += 1
			break

print( cnt )

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
n = int(raw_input())
S = map(int,raw_input().split())
q = int(raw_input())
T = map(int,raw_input().split())
C = 0

def binary_search(A,n):
    """no recursion version"""
    l = len(A)
    left = l/2
    right = l-1
    while A[left] != n:
        if left == right and A[left] != n:
            #print left,right,"if"
            return False
        elif A[left] > n: # n????????????????????´???
            right = left
            left = left/2
            #print left,right,"elif1"
        elif A[left] < n: # n????????????????????´???
            right = right
            left = (left + right-1)/2 + 1
            #print left,right,"elif2"
    else:
        return True

for item in T:
    if binary_search(S,item):
        C += 1
print C

Submission status: Accepted

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

c = 0
for t in T:
    left = 0
    right = n
    while left < right:
        mid = (left + right)/2
        if(S[mid] == t):
            c+=1
            break
        elif(t<S[mid]):
            right = mid
        else:
            left = mid+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:
n = input()
s = set(input().split())
q = input()
t = set(input().split())
print(len(s & t))

Submission status: Accepted

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

n = int(raw_input())
S = map(int, raw_input().split())
q = int(raw_input())
T = map(int, raw_input().split())
count = 0
for x in T:
    if binarySearch(x, S) >= 0:
        count += 1
print count

Submission status: Accepted

Solution code:
n = input()
S = set([int(s) for s in raw_input().split()])
m = input()
T = set([int(s) for s in raw_input().split()])
print len(T & S)

Submission status: Accepted

Solution code:
n = input()
S = map(int,raw_input().split())
m = input()
T = map(int,raw_input().split())
C=0
def binarySearch(A,p):
    lens = len(A)
    ll = -1
    ul = lens-1
    ms=(ll+ul)/2
    while (ll+1<ul):
    	ms=(ll+ul)/2
        if A[ms] >= p:
            ul =ms
        elif A[ms] < p:
            ll =ms
    return A[ul]==p

for item in T:
    if binarySearch(S,item):
        C += 1
print C

Submission status: Accepted

Solution code:
n = input()
S = set([int(s) for s in raw_input().split()])
m = input()
T = set([int(s) for s in raw_input().split()])
print len(S&T)

Submission status: Accepted

Solution code:
#coding:utf-8
#1_4_B
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(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 -1 #not found

ans = 0
n = int(input())
A = [int(x) for x in input().split()] 
z = int(input())
q = [int(x) for x in input().split()]
for x in q:
    tmp = binarySearch(A, x)
    if(tmp != -1):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n_1=input()
n_1_List=map(int,raw_input().split())
n_2=input()
n_2_List=map(int,raw_input().split())
n_1_List=set(n_1_List)
n_2_List=set(n_2_List)
print(len(n_1_List.intersection(n_2_List)))

Submission status: Accepted

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

import bisect


def isincluded(array, value):
    i = bisect.bisect_left(array, value)
    if i != len(array) and array[i] == value:
        return True
    else:
        return False


def main():
    n = int(input())
    s = [int(i) for i in input().split()]
    q = int(input())
    t = [int(j) for j in input().split()]
    print(sum(1 for x in t if isincluded(s, x)))


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 binary_search(A, key):
    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

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

print(cnt)

Submission status: Accepted

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

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

cnt = 0

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

print(cnt)

Submission status: Accepted

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

q = input()
T = tuple(map(int, input().split(' ')))

cnt = 0

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

print(cnt)

Submission status: Accepted

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

n = int(input())
S = tuple(map(int, input().split(' ')))

q = input()
T = tuple(map(int, input().split(' ')))

cnt = 0

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

print(cnt)

Submission status: Accepted

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

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

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

Submission status: Accepted

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


def binarySearch(A, key):
    left, right = 0, 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()))

count = 0

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

print (count)

Submission status: Accepted

Solution code:
def binarySearch(A, key, n):
    left = 0
    right = n
    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(input())
S = tuple(map(int, input().split(' ')))

q = input()
T = tuple(map(int, input().split(' ')))

cnt = 0

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

print(cnt)

Submission status: Accepted

Solution code:
iterator = (("NS", "S"), ("NT", "T"))
var = {}

for i, j in iterator:
    var[i] = int(input())
    var[j] = [int(k) for k in input().split()]

count = 0
for T in var["T"]:
    left = 0
    right = len(var["S"])
    while(left < right):
        mid = (left + right)//2
        if var["S"][mid] == T:
            count += 1
            break
        elif var["S"][mid] <= T:
            left = mid+1
        else:
            right = mid
print(count)

Submission status: Accepted

Solution code:
n = input()
  
S = [int(x) for x in raw_input().split()]
  
q = input()
  
T = [int(x) for x in raw_input().split()]
  
C = 0
 

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

print C

Submission status: Accepted

Solution code:
n = input()
  
S = [int(x) for x in raw_input().split()]
  
q = input()
  
T = [int(x) for x in raw_input().split()]
  
C = 0

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

print C

Submission status: Accepted

Solution code:
def gost(lis,ky,r,l):
    
    lens=l-r+1
    
    if lens <= 5:
        if ky in lis[r:l+1]:
            return True
        else:
            return False
    
    if ky <= lis[r+(lens//2)-1]:
        return gost(lis,ky,r,r+(lens//2)-1)
    else:
        return gost(lis,ky,r+(lens//2),l)
    

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

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


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

Submission status: Accepted

Solution code:
n = input()

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

q = input()

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

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

print cnt

Submission status: Accepted

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

# print(sum(i in s for i in t))
s.sort()


def binary_search(i):
    global s
    l, r = 0, len(s)
    while l < r:
        m = (l + r) // 2
        sm = s[m]
        if sm == i:
            return 1
        elif i < sm:
            r = m
        else:
            l = m + 1
    return 0


print(sum(binary_search(i) for i in t))

Submission status: Accepted

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

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 binarySearch(n, S, search):
    low    = 1 - 1
    high   = n - 1
    middle = 0

    while low < high:
        middle = (high + low)/2
        if S[middle] == search or S[low] == search or S[high] == search:
            return 1
        elif search < S[middle]:
            high = middle - 1
        elif S[middle] < search:
            low = middle + 1
    return 0

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

count = 0

for j in range(q):
    search = T[j]
    count = count + binarySearch(n, S, search)

print count

Submission status: Accepted

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

print len(S & T)

Submission status: Accepted

Solution code:
def binarySearch(key, lst):
    start = 0
    end = len(lst) - 1
    while end - start >= 0:
        i = (end - start) / 2 + start
        if lst[i] > key:
            end = i - 1
        elif lst[i] < key:
            start = i + 1
        else:
            del lst[i]
            return True
    return False

if __name__ == "__main__":
    input()
    S = map(int, raw_input().split())
    input()
    T = map(int, raw_input().split())

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

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

	cnt = 0
	for i in range(q):
		if (binarySearch(L, n, Key[i])):
			cnt += 1

	print(cnt)

Submission status: Accepted

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

def sort(a, left, right):
    if left < right:
        mid = (left+right)/2
        pivot = a[mid]
        a[mid] = a[left]
        p = left
        for i in range(left+1, right+1):
            if a[i] < pivot:
                p = p+1
                p, i = i, p
        a[left] = a[p]
        a[p] = pivot
        sort(a, left, p-1)
        sort(a, p+1, right)

def search(a, target):
    lo = 0
    hi = n-1
    while lo <= hi:
        mid = (lo+hi)/2
        if target <= a[mid]:
            hi = mid-1
        if target >= a[mid]:
            lo = mid+1
    if lo == hi+2:
        return True
    else:
        return False

n = int(raw_input())
S = map(int, raw_input().split())
q = int(raw_input())
T = map(int, raw_input().split())
count = 0
sort(S, 0, n-1)
for i in range(q):
    if search(S, T[i]):
        count += 1
print count

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def binary_search(key, a):
    l = 0
    r = len(a)
    ix = (r - l) // 2

    while r - l > 0:
        if key == a[ix]:
            return True

        if key < a[ix]:
            r = ix
        else:
            l = ix + 1
        ix = l + (r - l) // 2

    return False

if __name__ == '__main__':
    n = input()
    s = [int(x) for x in input().split()]
    q = input()
    t = [int(x) for x in input().split()]

    ans = 0
    for e in t:
        ans += 1 if binary_search(e, s) else 0

    print(ans)

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

if __name__=='__main__':
    n=int(input())
    S=list(map(int,input().split()))
    q=int(input())
    T=list(map(int,input().split()))
    cnt = 0
    print(sum(map(lambda t: binarySearch(S,t) >= 0, T)))

Submission status: Accepted

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

print len(T&S)

Submission status: Accepted

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


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


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

    count = 0
    for i in xrange(len(T)):
        if binary_search(T[i], S):
            count += 1
    print count

Submission status: Accepted

Solution code:
count_n = int(input())
N = []
n = input()
N = n.split()
N = list(map(lambda x: int(x), N))


count_p = int(input())
P = []
p = input()
P = p.split()
P = list(map(lambda x: int(x), P))


N.sort()
P.sort()


def b(i, l):
    left = 0
    right = len(l)
    while left < right:
        mid = int((left + right) / 2)
        if l[mid] > i:
            right = mid
        elif l[mid] < i:
            left = mid + 1
        elif l[mid] == i:
            return True
    return False
answer = 0
for p in P:
    if b(p, N):
        answer += 1
print (answer)

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(key, a, length):
    left = 0
    right = length
    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


cnt = 0
for i in T:
    if binarysearch(i, S, n):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp
sample_input = list(range(3))
sample_input[0] = '''5
1 2 3 4 5
3
3 4 1'''
sample_input[1] = '''3
1 2 3
1
5'''
sample_input[2] = ''''''
give_sample_input = None
if give_sample_input is not None:
    sample_input_list = sample_input[give_sample_input].split('\n')
    def input():
        return sample_input_list.pop(0)
        
# main
num_of_S = int(input())
S = list(map(int, input().split(' ')))
num_of_T = int(input())
T = list(map(int, input().split(' ')))

def binary_search(increasing_list, elem):
    index_min = 0
    index_max = num_of_S-1
    
    while index_max - index_min >= 2:
        index_middle = int((index_min + index_max) / 2)
        if increasing_list[index_middle] == elem:
            return True
        elif increasing_list[index_middle] > elem:
            index_max = index_middle
        else:
            index_min = index_middle
            
    if increasing_list[index_min] == elem:
        return True
    elif increasing_list[index_max] == elem:
        return True
    else:
        return False

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

Submission status: Accepted

Solution code:
def search(S,t):
    return _search(S,t,0,len(S)-1)

def _search(S,t,l,r):
    if l > r:
        return False
    m = (l+r)/2
    if S[m] == t:
        return True
    elif S[m] > t:
        return _search(S,t,l,m-1)
    else:
        return _search(S,t,m+1,r)


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


ret = 0
for t in T:
    if search(S,t):
        ret += 1
print ret

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def binary_search(array, value, begin, end):
    if begin >= end:
        return None
    else:
        next_index = begin + (end - begin) // 2
        if array[next_index] == value:
            return next_index
        elif array[next_index] < value:
            return binary_search(array, value, next_index + 1, end)
        else:
            return binary_search(array, value, begin, next_index)

def main():
    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:
        if binary_search(S, t, 0, len(S)) != None:
            count += 1

    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def binary_search(a, t, n):
    low = 0
    high = n - 1
    while low <= high:
        mid = (high + low) // 2
        if a[mid] == t:
            return True
        elif a[mid] < t:
            low = mid + 1
        else:
            high = mid - 1
    return False


def main():
    n = int(sys.stdin.readline())
    s = [int(x) for x in sys.stdin.readline().split()]
    q = int(sys.stdin.readline())
    t = [int(x) for x in sys.stdin.readline().split()]
    cnt = 0

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


if __name__ == '__main__':
    main()