이진 탐색: 백준 1920 파이썬

문제:

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

1920번: 수 찾기

 

정답:

import sys
n = int(sys.stdin.readline())
n_arr = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
m_arr = list(map(int, sys.stdin.readline().split()))


def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None


n_arr.sort()

for i in m_arr:
    result = binary_search(n_arr, i, 0, n-1)
    if result != None:
        print(1)
    else:
        print(0)

 

풀이:

이진 탐색 알고리즘을 사용해 간단하게 해결했다.

정수의 범위가 -2^31 보다 크거나 같고 2^31보다 작다.

탐색해야 하는 수의 범위가 큰 상황에서 탐색을 수행해야 하기 때문에 이진 탐색으로 문제에 접근했고, 정답을 맞혔다.