Problem Solving/Binary Search

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

by ggyongi 2021. 5. 22.

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

1920번: 수 찾기

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

www.acmicpc.net

n = int(input())
nums = list(map(int, input().split()))
nums.sort()

m = int(input())
targets = list(map(int, input().split()))

answer = [0]*m
for i in range(m):
    target = targets[i]
    left = 0
    right = len(nums)-1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else: # find
            answer[i] = 1
            break
print(*answer)