[이분탐색] 백준 10815. 숫자카드

문제

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

숫자가 카드안에 있는지 탐색하는 문제다. 문제조건에 두 숫자 배열의 크기가 50만이 넘기 때문에 find나 filter나 완전탐색으로 하면 시간초과가 뜨기 때문에 업다운 게임처럼 이분탐색으로 힌트를 줌으로써 탐색범위를 효과적으로 줄여야 한다.

코드

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

def binary(mid):
    return card[mid]

card.sort()
ans = []
for i in nums:
    l = 0
    r = n-1
    j = 0
    while l<=r:
        mid = (l+r)//2
        v = binary(mid)
        if v < i:
            l = mid+1
        elif v > i:
            r = mid-1
        else:
            j = 1
            break
    ans.append(j)
for a in ans:
    print(a, end=' ')