[BOJ] 수 찾기

---

코드

from sys import stdin
input = stdin.readline

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

arr = sorted(arr)

for num in tar:
    start, end = 0, N-1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == num:
            print(1)
            break
        if arr[mid] > num:
            end = mid - 1
        if arr[mid] < num:
            start = mid + 1
    if arr[mid] != num:
        print(0)

결과

풀이 방법

• 주어진 정수의 개수와 찾아야 할 정수의 개수가 모두 최대 100,000개이므로 순차탐색하면 시간초과가 날 것이다.
• 이분탐색을 활용하면 시간 안에 해결할 수 있을 것 같아서, 먼저 이분탐색을 위해 주어진 순열 A를 오름차순 정렬하고 시작하였다.
• 순열의 처음과 끝을 start, end로 세팅해놓고 중간값을 비교하면서 탐색 범위를 좁혀나간다.
• for문을 한 번 실행할 때마다 start, end를 순열의 처음과 끝으로 재설정해야 한다.

---