Problem Solving/Binary Search
[이진 탐색] 백준 1920번: 수 찾기
ggyongi
2021. 5. 22. 21:10
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)