BOJ 1920 수 찾기

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

input :

• 자연수 N (1 <= N <= 100,000)
• N개의 정수로 이루어진 리스트
• M (1 <= M <= 100,000
• M개의 수로 이루어진 리스트. [이 숫자들이 N개의 리스트에 존재하는지 핮으시오]

output :

• M개의 줄.
• 존재하면 1, 존재하지 않으면 0

---

동빈 선생님께서 큰 수들이 나오고, 탐색 시간을 줄일 때에는 이진 탐색(이분 탐색)을 쓰라고 하셨다. 기본 조건은 start가 end 보다 커지면 반복은 끝나는 것.
그리고 비교를 할 숫자 리스트는 언제나 정렬 되어 있어야 한다.

import sys

N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())
compare_num = list(map(int, sys.stdin.readline().split()))

**numbers.sort()**
#언제나 정렬 해 줘야 함.
possible = [False] * M

for target_idx in range(len(compare_num)):
    target = compare_num[target_idx]
    start = 0
    end = len(numbers) - 1

    while start <= end:
    # 종료 조건 start 가 end 보다 커질 때
        mid = (start + end) // 2
        if numbers[mid] == target:
            possible[target_idx] = True
            break
        elif numbers[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

for boolean in possible:
    if boolean:
        print(1)
    else:
        print(0)