[이코테] 이진 탐색_부품 찾기 (python)

juyeon·2022년 7월 5일
0

나의 풀이

1. for문 사용해서 풀기

n = int(input())
arr = list(map(int, input().split()))
m = int(input())
order = list(map(int, input().split()))

for i in range(m): #부품 리스트를 돌면서
    if order[i] in arr: #부품 리스트에 있다면
        print('yes', end = ' ')
    else: #부품 리스트에 없다면
        print('no', end = ' ')

2. 이진 탐색 이용해보기(재귀 함수로 구현)

def bin_search(arr, target, start, end):
    mid = (start + end) // 2 #중간점(index) 설정
    if start > end:  #타겟이 없을 경우
        return 'no'
    
    elif arr[mid] == target: #타겟을 찾음
        return 'yes'
        
    elif arr[mid] > target: #중간점이 타겟보다 크다면
        return bin_search(arr, target, start, mid - 1)
    
    else: #중간점이 타겟보다 작다면
        return bin_search(arr, target, mid + 1, end)
        
n = int(input())
arr = sorted(list(map(int, input().split())))
m = int(input())
order = sorted(list(map(int, input().split())))

for target in order:
    print(bin_search(arr, target, 0, n - 1), end = ' ')

: mid를 min으로 오타내는 바람에.. 계속 오류 나서 얼마나 고생했는지ㅠㅠ

  • if start > end
    : 타겟이 없으면 start = end = mid가 되고, 여기서 한번 더 재귀함수 돌면서 결국 start > end가 됨~
profile
내 인생의 주연

0개의 댓글