[백준] 1920 파이썬

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

문제 해결 과정
1. 문제의 조건을 보면 N, M이 각각 최대 100,000이 될 수 있다. 이때 Python list 자료형의 in 함수를 사용한다면 코드의 최대 반복 횟수는 100,000^2가 된다.
2. 따라서 이 문제를 해결하기 위해서는 이진 탐색을 사용해야 한다.
3. 이진 탐색의 조건은 탐색하고자 하는 데이터가 정렬되어 있어야 하므로 N_lst를 먼저 정렬했다. Python의 sort 함수들은 tim sort(nlogn)로 구현되어 있기 때문에 이 문제에서 사용할 수 있다.
4.이제 M_lst의 숫자들이 N_lst에 존재하는지 이진 탐색을 통해 확인하면 된다.

import sys
input = sys.stdin.readline

N = int(input())
N_lst = sorted(map(int, input().split()))
M = int(input())
M_lst = list(map(int, input().split()))


def binary_search(start, end, target):
    while start <= end:
        middle = (start + end) // 2
        if N_lst[middle] == target:
            return True
        elif N_lst[middle] > target:
            end = middle - 1
        else:
            start = middle + 1
    return False


for m in M_lst:
    if binary_search(0, N - 1, m):
        print(1)
    else:
        print(0)