[백준] 10815 숫자카드 in Python : 이진탐색으로 시간단축하기

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

10815번: 숫자 카드

 

이진탐색의 시간 복잡도는 O(logN)으로 선형탐색 O(n) 을 사용할 때보다 시간을 단축할 수 있다 

# 10815 숫자카드

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

def bisect(left, right, target):

    if left > right:
        return None
    mid = (left + right) // 2
    if target == card[mid]:
        return mid
    elif card[mid] < target:
        return bisect(mid+1, right, target)
    else:
        return bisect(left, mid - 1, target)

for i in find:
    result = bisect(0, n-1, i)
    if result == None:
        print('0',end=' ')
    else:
        print('1', end=' ')