[백준] 1920번 - 수 찾기

---

문제 분석

주어진 N의 최대 범위가 100,000이므로 O(nlogn) 시간 복잡도로 해결할 수 있다.
이진탐색의 시간복잡도는 O(logn)이므로 주어진 M개의 숫자를 순서대로 보면서, A배열에서의 이진 탐색을 진행하면 O(nlogn)의 시간 복잡도로 해결이 가능하다.

---

소스 코드

# 수 찾기

import sys
input = sys.stdin.readline

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

arr.sort()


def find(num):
    pl = 0
    pr = N - 1
    success = False

    while pl <= pr:
        x = (pl + pr) // 2
        if arr[x] == num:
            success = True
            break
        elif arr[x] > num:
            pr = x - 1
        else:
            pl = x + 1
    if success:
        print(1)
    else:
        print(0)


for v in findNumber:
    find(v)