백준 1920번 - 수 찾기 [python/파이썬]

 

이분탐색 (Binary Search)를 이용한 문제

이분탐색이란 우리가 일반적으로 업다운 문제를 풀 때의 원리와 똑같다.

1에서 100까지의 수 중 74라는 숫자를 맞추기 위해 우리는 먼저 50을 부른다.

up이 나오면 그 다음에는 50과 100의 중앙값인 75를 부른다. 이를 반복하면 74라는 숫자를 찾을 수 있다.

 

import sys
 
N = int(input())
num_list1 = list(map(int, sys.stdin.readline().strip().split()))
num_list1.sort()
 
M = int(input())
num_list2 = list(map(int, sys.stdin.readline().strip().split()))
 
 
def binarySearch(num, start, end):
    while start <= end:
        mid = (end + start)//2
        if num > num_list1[mid]:
            start = mid + 1
        elif num < num_list1[mid]:
            end = mid - 1
        else:  # num == num_list1[mid]
            return True
    return False
 
 
for num in num_list2:
    if binarySearch(num, 0, len(num_list1)-1):
        print(1)
    else:
        print(0)