1920번: 수 찾기

import sys
sys.setrecursionlimit(10 ** 6)

# 병합 정렬
def merge_sort(arr):

    if len(arr) < 2:
        return arr

    mid = len(arr)//2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0

    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1

    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]

    return merged_arr

# 이진 탐색
def search(arr, start, end, search_data):
    # arr(n_number_list)은 배열 start는 시작 인덱스 end는 끝 인덱스

    if start == end: # 배열의 길이가 1이라면
        if arr[start] == search_data:
            return 1
        else:
            return 0

    mid = len(arr)//2

    if arr[mid] < search_data:
        return search(arr, mid + 1, end, search_data)
    else:
        return search(arr, start, mid, search_data)

n = int(sys.stdin.readline().strip())
n_number_list = list(map(int, sys.stdin.readline().split()))
n_number_list = merge_sort(n_number_list)

m = int(sys.stdin.readline().strip())
m_number_list = list(map(int, sys.stdin.readline().split()))

for number in m_number_list:
    print(search(n_number_list, 0, len(n_number_list)-1, number))