수 찾기 - 1920번

단순하게 배열에 있는지 없는지를 따지게 되면 시간초과가 뜨는 문제이다.

탐색 중, 이분탐색을 사용하여 풀면 빠르다.

문제 해결을 위해 이분탐색하는 함수를 만들어주었다. return값은 인덱스를 뽑아낸다.

 

n = int(input())
ns = list(map(int,input().split()))
m = int(input())
ms = list(map(int,input().split()))
ns.sort()

# 이분탐색 함수
def bin_search(target, arr):
    start = 0
    end = len(arr)-1

    while start <= end:
        mid = (start+end)//2

        if arr[mid] == target:
            return mid
        elif arr[mid]>target:
            end = mid-1
        else:
            start = mid+1
    return None

for i in ms:
    idx = bin_search(i,ns)
    if idx != None:
        print(1)
    else:
        print(0)