이진 탐색
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법

✅ 문제

전자 매장에는 부품이 N개 있고, 각 부품은 정수 형태의 고유한 번호가 있다. 부품 M개 종류가 모두 있는지 확인하는 프로그램을 작성해보자.

입력 예시

5
8 3 7 9 2
3
5 7 9

출력 예시

no yes yes

💻 코드

N = int(input())
N_list = list(map(int, input().split()))

M = int(input())
M_list = list(map(int, input().split()))


for i in M_list:
    if i in N_list:
        print("yes", end= ' ')
    else:
        print("no", end = ' ')

설계

이진 탐색으로 풀지 않고 단순히 부품 M개 중에 하나가 부품 N개 중에 있으면 (if in 문 사용) yes를 출력하고, 없다면 no를 출력하게 하였다.

➕ 다른 풀이

이진 탐색으로 부품 M개 중에서 부품 N개 안에 부품이 있는지 확인한다.

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

N = int(input())
N_list = list(map(int, input().split()))

N_list.sort()

M = int(input())
M_list = list(map(int, input().split()))

for i in M_list:
    result = binary_search(N_list, i, 0, N - 1)
    if result != None:
        print("yes", end=' ')
    else : 
        print("no", end=' ')