[알고리즘]백준 1920번: 수 찾기

 

문제

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

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

 

배열 안에 숫자가 존재하는지 탐색하는 알고리즘입니다. 

간단하게 if not in 이나 in을 사용하게 되면 배열의 범위가 100,000까지이므로 시간 초과를 피할 수 없습니다 

그렇기 때문에 이진탐색 알고리즘을 통해 문제를 해결하겠습니다 

 

 

https://kjim.tistory.com/38

[알고리즘]이진 탐색(binary search) 알고리즘(+python구현)

자세한 내용은 위 포스팅 참고하시면 좋을거 같스빈다 

 

 

def binary_search(arr, target, start, end):
    
        while start<= end: 
            mid = (start+end)//2 
            if arr[mid]==target:
                return 1 
            elif arr[mid]>target: 
                end = mid- 1

            elif arr[mid]<target: 
                start =mid+ 1 

        return 0 
import sys 

N = int(sys.stdin.readline().strip())
arr = map(int, sys.stdin.readline().strip().split(" ")) 
M = int(sys.stdin.readline().strip())
target = map(int, sys.stdin.readline().strip().split(" "))

arr = sorted(arr)

for i in target:
    print(binary_search(arr,i,0, len(arr)-1))