[이진탐색] 부품찾기

1. 문제 설명

- 부품 리스트의 배열과 찾는 부품에 해당하는 두 배열이 주어지고, 부품 리스트에 찾는 부품이 있는지를 확인하는 문제

2. 코드

# 입력
N = int(input())
array1 = list(map(int, input().split()))
array1.sort()

M = int(input())
array2 = list(map(int, input().split()))
array2.sort()

"""
5
8 3 7 9 2
3
3 9 7
"""

# 이진탐색
def binary_search(array, target, start, end):
    mid = (start+end)//2
    if start > end:
        return None
    if array[mid]==target:
            return True
    elif   target < array[mid]:
        return binary_search(array, target, start, mid-1)
    else:
        return binary_search(array, target, mid+1, end)    

# 출력
def parts(N, array1, M, array2):
    for i in array2:
        result = binary_search(array1, i, 0, N-1)
        if result != None:
            print("yes", end=" ")
        else:
            print("no", end= " ")
            
parts(N, array1, M, array2)
# >> yes yes yes

3. 코멘트

- in을 사용해서 문제를 풀 수도 있어보인다. 하지만 더 큰 데이터가 주어질 때 더 수월하게 찾을 수 있기에 binary_search로 구현한 것 같다. 

- binary_search는 재귀적으로 구현된다는 점을 기억하자.