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

이진탐색(binary search)를 통해서 풀 수 있는 문제다.

 

이진탐색을 사용할 수 있는 조건은 배열이 정렬이 된 상태에서 사용할 수 있다.

또한 이진탐색은 순차적으로 탐색하는 방법보다 훨씬 빠르게 원하는 값을 찾아낼 수 있다.

시간복잡도 -> O(logN)

탐색해야하는 숫자의 수가 절반씩 줄어들기 때문에!

 

이진탐색은 반복문 말고도 재귀를 사용하여 구현할 수 있다.

두가지 모두 알아두고 구현해낼 수 있도록 연습해야겠다. 

# 1920 수 찾기

n = int(input())
list_n = list(map(int, input().split()))
list_n.sort()
m = int(input())
list_m = 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 mid+1
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return None

for target in list_m:
    if binary_search(list_n,target):
        print(1)
    else:
        print(0)