백준_1920_수 찾기

문제

1920번: 수 찾기

풀이

이분 탐색을 이용하여 위의 문제를 해결할 수 있다. 이를 위하여 우선 첫번째 배열을 오름차순으로 정렬해야 한다. 그 뒤에 다음에 따라 특정 수가 존재할 수 있는 짧은 구간[start, end]을 찾는다. 

 

1. [start, end]의 중간 점을 p라고 할때, arr1의 p번째 원소가 찾으려는 값 number보다 크거나 같다면 탐색구간을 [start, p]로 줄인다.

2. arr1의 p번째 원소가 찾으려는 값 number보다 작다면 탐색구간을 [p, end]로 줄인다.

 

arr1[start]와 arr1[end]에 찾으려는 값 number이 존재한다면 1을 아니라면 0을 출력한다.

코드

N = int(input())
arr1 = list(map(int, input().split()))
M = int(input())
arr2 = list(map(int, input().split()))

arr1.sort()
for i in range(M) :
    number = arr2[i]

    # 이분 탐색
    start, end = 0, N-1
    while end-start>1 :
        p = int((start+end)/2)
        if arr1[p]>=number : end = p
        elif arr1[p]<number : start = p

    # 답 찾기
    if arr1[start]==number or arr1[end]==number : print(1)
    else : print(0)