1920 수 찾기

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

def binary_search(array,target,start_idx,end_idx):

    if start_idx > end_idx :
        return False
    mid_idx = (start_idx+end_idx)//2

    # mid_idx가 target과 일치하면 True 반환
    # 이 조건이 recursive를 끝내는 주 조건문이 된다.

    if target == array[mid_idx]:
        return True

    # mid보다 target이 왼쪽에 있을 경우(작을경우) end idx를 mid idx로 업데이트 후 recursive 실행
    elif target < array[mid_idx] :
        return binary_search(array,target,start_idx,mid_idx-1)
    elif target > array[mid_idx] :
        return binary_search(array,target,mid_idx+1,end_idx)

import sys
read = sys.stdin.readline

N = int(input())
N_array = list(map(int,read().split()))

# 이진 탐색에서 핵심은 array를 오름차순으로 정렬하는 것!!
# 어차피 지금 문제는 수가 있냐 없냐를 표현하는 것이므로 정렬하자!
N_array.sort()

M = int(read())
M_array = list(map(int,read().split()))


for i in range(M):
    target = M_array[i]
    print(int(binary_search(N_array,target,0,N-1)))

3. 문제 풀이

이진 탐색도 안하려고 했으나, 다 해야겠다고 생각! 그래서 오늘부터 문제풀이에 들어간다. 이게 안했으면 큰일 났을 것 같다. 책을 다시보니 자주 나오는 유형이란다 ㅎㅎ

이진 탐색의 가장 기본은 배열을 정렬하는 것이다. 그래야 올바른 이진 탐색이 된다. 위 문제를 풀 때, 그걸 안해서 계속 헤맸다. ㅜㅜ;

그리고 mid_idx에서 1을 빼거나 더한 것으로 recursive를 들어가야 계속해서 무한 루프를 돌지 않는 듯 하다. 빼거나 더해야지 최종적으로 mid_idx가 start_idx 혹은 end_idx로 수렴하거나, 아예 찾지 못하는 3가지의 경우로 나뉘기 때문에 필수적으로 해야한다. 이제 이진 탐색도 체화하도록 하자.