[Python/이진탐색] 1920 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예시 입력	예시 출력
5 4 1 5 2 3 5 1 3 7 9 5	1 1 0 0 1

---

풀이

문제를 보자마자 두번째 줄에 입력받은 N의 리스트를 정렬하고 이진탐색으로 M의 원소들이 N의 리스트에 존재하는 지 찾으면 되겠다고 생각

import sys
input = sys.stdin.readline

N = int(input())
N_arr = sorted(list(map(int, input().split())))
M = int(input())
M_arr = list(map(int, input().split()))

# M_arr을 순회하며 N_arr에 존재하는 지 확인
for m in M_arr:
    start = 0
    end = N-1
    answer = -1
    while start <= end: # *** 종료 조건
        mid = (start + end)//2
        if N_arr[mid] == m:
            answer = 1
            break
        elif N_arr[mid] < m : #찾고자 하는 값이 더 큼
            start = mid + 1
        else: # 찾고자 하는 값이 더 작음
            end = mid-1
    if answer == 1:
        print(1)
    else:
        print(0)