[이진탐색] 백준 Silver 4 1920 수 찾기 (Python 파이썬)

💡문제 링크

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

 

💡문제 분석 요약

N개의 정수가 주어졌을 때(A), 특정 정수가 A 안에 있는지 판단하는 문제

특정 정수가 A 안에 존재하면 1을, 존재하지 않으면 0을 출력한다.

예를 들어, A = [1, 2, 4, 8, 9, 10]일 때, 9는 A 안에 있으므로 1을 출력, 7은 A 안에 없으므로 1을 출력

 

💡알고리즘 설계

처음에 단순히 앞에서부터 차례대로 순서 탐색하는 일차원적인 생각을 했다.

"당연히" 런타임 에러가 떴다. ( 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. )

그래서 '아 그냥 무작정 탐색은 안되겠구나. 이진 탐색을 해야겠다' 라고 생각했다.

이진 탐색은 여러 번 공부해서 개념이 머리에 잡혀있던 터라 그냥 코드를 적었다.

 

💡코드

n = int(input())
A = sorted(list(map(int, input().split())))
m = int(input())
search_list = list(map(int, input().split()))

def binary_search(array, key, start, end):
    if (start <= end):
        mid = (start + end) // 2
        if key == array[mid]:
            print(1)
            return
        elif key < array[mid]:
            binary_search(array, key, start, mid - 1)
        else:
            binary_search(array, key, mid + 1, end)
    else:
        print(0)

for s in search_list:
    binary_search(A, s, 0, len(A)-1)

 

💡 오답 풀이

처음에 부등호만 쓰고 등호를 안 써서 틀렸다.

def binary_search(array, key, start, end):
    if (start < end):

이진탐색을 반복적으로 진행하다가 결국 start = end가 되어서 탐색대상이 하나밖에 안 남았을 때,
그리고 그 하나 남은 탐색 대상이 key일 때 if (start <= end):로 써야 아래 코드로 들어가서 1을 출력할 수 있다.

        if key == array[mid]:
            print(1)
            return

만약 오답 풀이처럼 if (start < end): 라면,
결국 start = end가 되어서 탐색대상이 하나밖에 안 남았을 때, 그냥 밖으로 나가서 0을 출력하게 된다.

예를 들어 8을 탐색하는 경우 이진탐색을 반복적으로 진행하다가 결국 8밖에 안남았는데,
8을 탐색하지 않고 0을 출력해버리는 꼴이다.

마지막 코드에 len(A)로 써서 틀렸다.

for s in search_list:
    binary_search(A, s, 0, len(A))

맨 마지막 원소의 인덱스는 len(A) - 1이다!!!

💡 다른 풀이

N = int(input())
A = list(map(int, input().split()))
M = int(input())
arr = list(map(int, input().split()))
A.sort()

for num in arr:
    lt = 0
    rt = N - 1
    isExist = False

    while lt <= rt:
        mid = (lt + rt) // 2
        
        if num == A[mid]:
            isExist = True
            print(1)
            break
        
        elif num > A[mid]:
            lt = mid + 1
            
        else:
            rt = mid - 1

    if not isExist:
        print(0)

다른 점 1: 나는 바로 sort문을 써서 A 배열을 정렬했는데, 이 코드에서는 A.sort()로 두 줄에 걸쳐서 작성

다른 점 2: 나는 재귀함수로 반복했는데, 이 코드는 for, while로 썼다. 

 

💡 느낀점 or 기억할정보

나는 for, while보다 재귀함수가 더 편한 것 같다..