Chapter 07 이진 탐색 - 부품 찾기

https://www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

[197p 부품 찾기]

 

import sys

n = int(sys.stdin.readline().rstrip())
stores = list(map(int, sys.stdin.readline().rstrip().split()))[:n]
m = int(sys.stdin.readline().rstrip())
parts = list(map(int, sys.stdin.readline().rstrip().split()))[:m]

# 이진 탐색을 위한 정렬
stores.sort()


# 이진 탐색
def binary_search(array, target, start, end):
    if start > end:
        return

    mid = (start + end) // 2

    # 값을 찾았다면
    if array[mid] == target:
        return mid
    # 찾고자 하는 값이 현재 값보다 작으면
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 찾고자 하는 값이 현재 값보다 크면
    else:
        return binary_search(array, target, mid + 1, end)


for part in parts:
    if binary_search(stores, part, 0, n - 1):
        print('yes', end=" ")
    else:
        print('no', end=" ")