[Binary Search] python 10815 숫자 카드

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

10815번: 숫자 카드

# 2023.02.05
import sys
input = sys.stdin.readline

n = int(input()) # 숫자 카드의 개수
nCard = sorted(list(map(int, input().split()))) # 숫자 카드
m = int(input()) # 확인할 숫자카드의 개수
mCard = list(map(int, input().split())) # 확인할 숫자 카드

answer = [] # 상근이가 가지고 있으면 1, 아니면 0
for findingCard in mCard:
    start, end = 0, n-1
    while start<=end:
        mid = (start+end)//2
        if nCard[mid]==findingCard:
            answer.append("1")
            break
        elif nCard[mid]>findingCard: # 찾는 값보다 현재 indexd의 값이 더 크면
            end = mid-1
        elif nCard[mid]<findingCard:
            start=mid+1
    else:
        answer.append("0")

print(*answer)

 

완전 탐색으로 구하면 O(N) 시간초과

이분 탐색으로 하면 O(logN) OK

 

start와 end를 지정

start와 end가 역전하면 while문을 빠져나감

현재 check하고 있는 값(nCard[mid]) = findingCard라면 append후 while문을 빠져나감

현재 check하고 있는 값(nCard[mid]) > findingCard라면 왼쪽 절반을 탐색해야 함

현재 check하고 있는 값(nCard[mid]) < findingCard라면 오른쪽 절반을 탐색해야 함

 

while문 내에서 break문을 만나지 않고 while문을 나가게 되었다면 else문을 만남