BOJ1920 - 수 찾기

문제1920

문제

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

해결

• 문제를 좀더 손쉽게 해결하기 위해서는 이분 탐색을 통한 방법을 사용해야 한다.
• 첫번쨰 로 입력받은 수는 전부 정렬을 수행해야 한다
• 현재 A[N] 과 target 을 계속해서 비교하면서 범위를 좁혀 가면서 같은 수를 찾아야 한다.
• 이때 해당 숫자가 A[1] ~ A[N] 까지 없으면 0 을 출력해야 한다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

n = int(input())
nums = list(map(int, input().split()))
m = int(input())
targets = list(map(int, input().split()))

nums.sort()

for target in targets:
    answer = 0
    start = 0
    end = len(nums)-1
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] == target:
            answer = 1
            break
        elif nums[mid] < target:
            start = mid + 1
            continue
        else:
            end = mid-1 # mid 도 포함이 안되어있기 때문에 뺴도 된다.
            continue

    print(answer)