#198 백준 파이썬 [1920] 수 찾기 - 이분 탐색

https://www.acmicpc.net/problem/1920

 

#Solution

첫 리스트를 오름차순으로 정렬한 뒤, 두번째 리스트 요소 하나하나씩 이진 탐색으로 탐색해준다.

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 참고

def BinarySearch(arr, val, low, high):
    if low > high:
        return False
    
    mid = (low + high) // 2
    if arr[mid] > val:
        return BinarySearch(arr, val, low, mid - 1)
    elif arr[mid] < val:
        return BinarySearch(arr, val, mid + 1, high)
    else:
        return True

N = int(input())
A = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))
A = sorted(A)     

for m in M_list:
    if BinarySearch(A, m, 0, N-1):
        print(1)
    else:
        print(0)