<백준 문제풀이: 1920번> 파이썬 - 수 찾기

이분 탐색을 이용한 수 찾기 문제이다.

import sys

n = int(sys.stdin.readline())
N = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
M = list(map(int, sys.stdin.readline().split()))
N = sorted(N)

def binary_search(start, end, target, data):
    if start > end:
        return False
    mid = (start + end) // 2
    if data[mid] == target:
        return True
    elif data[mid] > target:
        return binary_search(start, mid - 1, target, data)
    elif data[mid] < target:
        return binary_search(mid + 1, end, target, data)

for i in M:
    if binary_search(0, n-1, i, N):
        print(1)
    else:
        print(0)

이분 탐색은 다른 탐색과 비슷한 알고리즘이나, 단순히 이분 - 즉 절반, 가운데를 확인하면서 그에 따라 탐색을 진행하는 알고리즘이다. 위의 binary_search를 본다면, 처음에 주어진 start 와 end를 기준으로, mid를 그 둘을 더하고 2로 나눈 몫의 값으로 저장시켜준다. 이후, 입력한 data 배열에 mid번째가 우리가 입력한 target과 같은지 아닌지 확인을 하고, 그에 따라 재귀를 이용하여 binary_search를 지속적으로 실행시켜준다. 이 함수를 빠져나오는 조건은 start 가 end보다 커졌을 때이다. 마지막으로, M 배열에 있는 요소들을 각각 binary_search를 시켜주고, 이에 따라 1 또는 0 을 출력해준다.