BOJ 1920번: 수 찾기

호프 2021. 1. 25. 02:00

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

아이디어:

이분 탐색의 기본 문제. 이분탐색의 로직을 잘 익히자.

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()

m = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))

for k in num:
    ans = 0
    high = n-1
    low = 0
    while (high>=low):
        mid = (high+low)//2 ##
        if (arr[mid]>k):
            high = mid-1
        elif (arr[mid]<k):
            low = mid+1
        else:
            ans = 1
            break
    print(ans)