백준 10815 파이썬(이분탐색)

이분탐색(binary search)를 이용해서 풀었다.

 

이분탐색은 탐색 기법중 하나로 말 그대로 탐색범위를 두 부분으로 나눠서 원하는 값을 찾는 방식이다.

탐색 범위를 절반씩 줄여가면서 찾는 탐색방법이다.

따라서 시간복잡도가 하나하나 일일이 탐색하는 순차탐색보다 더 좋다.

시간복잡도 : O(logN)

이분탐색을 할 때는 먼저 정렬이 된 상태이어야 한다.

dynamic programming, recursion의 개념이 녹아있다.

 

이분탐색 함수를 따로 정의해주고

찾아야할 리스트는 파이썬 함수로 정렬해주었다.

# 10815번: 숫자 카드

n = int(input())
n_list = list(map(int,input().split()))
m = int(input())
m_list = list(map(int,input().split()))

def binary_search(data,target):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2
        
        if data[mid] == target:
            return True
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return None

n_list.sort()
for i in m_list:
    if binary_search(n_list,i):
        print(1,end=' ')
    else:
        print(0,end=' ')