부품찾기 : 이진탐색

main 함수 로직

1. N 입력받기 : 가게에 있는 부품 갯수
   n(list) 입력받기 : 부품의 고유번호
2. M 입력받기: 손님이 요청한 부품 갯수
   m(list) : 부품의 고유 번호
3. n리스트 정렬시켜주기
4. for j in range(len(m)): 리스트 엠을 하나씩 찾아서
   result = binary_search(시작점,끝점,찾는데이터,리스트)
5. binary_serarch() 함수의 결과 값에 따라 yes,no 출력
   if(result=='yes')
   print('yes')
   else:
   print('no')

binary_search 함수 로직

1. 시작점이 끝점보다 크면 함수종료
   if(start>end)
   return no
2. 중간값 찾기
   mid = (start+end)//2
3. 중간값 == target 이면 함수종료
4. 중간값의 값이 찾는데이터보다 크면 끝점 이동
   if(n[mid] > target)
   binsary_search(start,mid-1,target,n)
5. 중간값의 값이 찾는 데이터보다 작으면 시작점 이동
   if(n[mid] < target)
   binary_search(mid+1,end,target,n)

코드

• 이진탐색을 실행하기 전, 가장 중요한 것은 리스트가 정렬되어 있어야 한다는 점 이다!!

def binary_search(start,end,target,list) :
  if start>end :
    return 'no'

  mid = (start+end)//2
  
  if target==list[mid] :
    return 'yes'

  if list[mid] > target:
    return binary_search(start,mid-1,target,list)
  if list[mid] < target:
    return binary_search(mid+1,end,target,list)

  

import sys    
N = int(input())
n = list(map(int,sys.stdin.readline().split()))
M = int(input())
m = list(map(int,sys.stdin.readline().split()))

n.sort()
for j in range(len(m)):
  result = binary_search(0,len(n),m[j],n)
  if result=='yes':
    print('yes', end=' ')
  else:
    print('no', end=' ')