[Algorithm][이진탐색] 백준 1920 : 수찾기

"""
1. 아이디어
- N개의 수 먼저 정렬
- M개를 for문 돌면서, 이진탐색
- 이진탐색 안에서 데이터를 찾으면 1출력, 아니면 0출력

2. 시간복잡도
일반) O(N*M) = 1e5 * 1e5 = 1e10 (100억) >> 2억 초과 !
이진탐색 개선) 
- N개의 입력값 정렬 : O(N*logN)
- M개를 N개 중에서 이진탐색 : O(M*logN)
- 총합 : O((N+M)*logN)=(2e5)*20=4e6 => 가능!

3. 자료구조
- N개 숫자 : int[]
    - 모든 수 범위: -2^31 <= < 2^31 (int로 가능)
- M개 숫자 : int[]
    - 모든 수 범위: -2^31 <= < 2^31 (int로 가능)
"""
""" input
5
4 1 5 2 3
5
1 3 7 9 5
"""
import sys
input = sys.stdin.readline

N = int(input())
arrN = sorted(list(map(int, input().split()))) #이진탐색 가능
M = int(input())
arrM = list(map(int, input().split()))


#search
def search(st, en, target):
    if st == en:
        if arrN[st] == target: 
            return 1
        else: 
            return 0
    mid = (st+en) // 2
    if arrN[mid] < target:
        return search(mid+1, en, target)
    else: 
        return search(st, mid, target)

for i in arrM:
    # 일반 탐색 : if i in arrN:
    print(search(0, N-1, i))

 

 

참고 - https://www.youtube.com/watch?v=D1ad7UCbWHY&list=PLi-xJrVzQaxXC2Aausv_6mlOZZ2g2J6YB&index=7