[백준 파이썬] # 1920 수 찾기

Silver IV

# 1920 수 찾기

링크 : https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

풀이_재귀적 구현

N = int(input())
N_li = list(map(int, input().split()))
M = int(input())
M_li = list(map(int, input().split()))

N_li.sort()

def binary_search(array, target, start, end):
    if start > end:
        return 0

    mid = (start+end) // 2

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

for i in M_li:
    print(binary_search(N_li, i, 0, N-1))

 

풀이_반복문 구현

N = int(input())
N_li = list(map(int, input().split()))
M = int(input())
M_li = list(map(int, input().split()))

N_li.sort()

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end)//2

        if array[mid] == target:
            return 1
        elif array[mid] > target:
            end = mid-1
        elif array[mid] < target:  # else문으로 대체 가능
            start = mid+1
    return 0

for i in M_li:
    print(binary_search(N_li, i, 0, N-1))

 

후기

• 나동빈님의 이코테 이진탐색 편을 참고했다. 처음 푸는 이진탐색 문제라 최대한 같은 코드를 사용해서 풀어보았다.
  
  
• 이진탐색 풀이의 두 가지 방식(재귀적 구현, 반복문 구현)을 모두 연습해보았다.
  개인적으로는 반복문을 활용한 방법이 더 직관적으로 이해되서 반복문을 주로 사용할 듯
  
  
• print 문에서 end값을 N-1으로 설정해야 한다 : 리스트의 마지막 인덱스
  N = 5일 때, N_li 인덱스 = [0, 1, 2, 3, 4] : 4 = 5-1 = N-1