[Python]이분탐색 백준 1920

문제

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

가장기본적인 이분탐색이다.

각단계마다 반씩 줄어들어서 logN만큼의 시간이 소요된다.

A를 정렬하고 각 수가 주어질때마다 A의 중앙값보다 작다면 앞에서 크다면 뒤에서 다시 

이분탐색을 시행한다.

import sys
 
def binary_search(start,end,M):
    if start>end:
        return 0
 
    mid=(start+end)//2
 
    if A[mid]==M:#같다면 서치종료
        return 1
    elif A[mid]>M:#M이 중앙값보다 작다면 앞에서 비교
        return binary_search(start,mid-1,M)
    else:#크다면 뒤에서 비교
        return binary_search(mid+1,end,M)
 
 
N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
 
M=int(sys.stdin.readline())
B=list(map(int,sys.stdin.readline().split()))
 
 
A=sorted(A)#A정렬
for i in range(M):
    if binary_search(0,N-1,B[i]):
        print(1)
    else:
        print(0)