백준 1920번. 수 찾기 (Python / 파이썬)

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31보다 크거나 같고 2^31보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

---

문제 풀이

수 찾기 문제는 N개의 정수가 주어졌을 때, 그 안에 X라는 정수가 존재하는지 탐색하는 문제입니다.

문제에서 주어진 입력을 보면 정수의 범위가 매우 큽니다.

따라서 완전 탐색으로 문제를 해결하기엔 시간 소요가 클 것으로 예상 됩니다.

이진 탐색 (Binary Search) 으로 문제를 해결하면 훨씬 빠르게 수를 탐색할 수 있습니다. 

 

이때, 주의해야 할 점은 이진 탐색은 정렬 된 상태에서만 가능하다는 것입니다.

따라서 꼭!! 탐색할 배열을 정렬해주어야 합니다.

 

이진 탐색은 mid 값을 설정해주고, mid 값을 상황에 따라 적절히 조절해주어 

mid index에 해당하는 값이 찾고자 하는 target과 같아졌을 때 값을 return 해주는 알고리즘입니다.

만약 찾지 못했다면 None을 return 해줍니다.

정확한 알고리즘은 아래 코드에서 이진 탐색 함수를 참고해주세요!

 

 찾고자 하는 값의 배열에서 하나씩 이진 탐색을 수행하여

만약 None 을 반환하면 0을 출력하도록, 

 그렇지 않다면 1을 출력하도록 해주었습니다.

---

My Code

# 이진 탐색 함수
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

n = int(input())
array = list(map(int,input().split()))
array.sort() # 이진 탐색 위해 정렬 

m = int(input())
target = list(map(int,input().split()))

for tg in target: # target 값을 하나씩 확인
    result = binary_search(array, tg, 0, n - 1)
    if result == None: 
        print(0)
    else:
        print(1)