[정글 week02] 백준 코테 수 찾기 1920

N = int(input())
n_list = list(map(int, input().split()))
M = int(input())
m_list = list(map(int, input().split()))
n_list.sort()

def bin_search(n, target, start, end):
    
    if start > end:
        print(0)
        return
    
    mid = (start + end) // 2

    if target == n[mid]:
        print(1)
        return
    elif n[mid] < target:
        bin_search(n, target, mid+1, end)
    elif n[mid] > target:
        bin_search(n, target, start, mid-1)


for i in range(len(m_list)):
    target = m_list[i]
    bin_search(n_list, target, 0, len(n_list)-1) 

사용 알고리즘
이진 탐색

시간 복잡도
sort() : O(n log n)

m_list(반복) + bin_search() : O(m + log n)

최종
: O(n log n)