[백준-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을 출력한다.

 

예제 입력

5
4 1 5 2 3
5
1 3 7 9 5

 

예제 출력

1
1
0
0
1

---

문제 요약

• 두 정수 배열 A(길이 N), B(길이 M)가 주어짐.
• 배열 B의 각 원소가 배열 A에 존재하는지 여부(1 또는 0) 를 출력하는 문제.

핵심 아이디어: 이진 탐색 (Binary Search)

정렬된 배열에서 특정 값을 빠르게 찾기 위한 탐색 알고리즘
시간복잡도: O(log N) → 전체 문제는 O(M log N)

 

---

코드작성

import sys # 빠른 입출력을 위한 방법
input = sys.stdin.readline

# A[n] 의 정수 값 받기
n = int(input())
# A[n] 원소값 입력 받기
num = list(map(int, input().split()))
# 이진탐색을 위해 정렬
num.sort()

# 찾고자 하는 정수값 받기
m = int(input())
# 찾고자하는 숫자 원소값 받기
find_num = list(map(int,input().split()))

# 이진탐색시작
for i in find_num : # find_num 원소를 돌면서 i에 집어넣기
    lp, rp = 0, len(num)-1 # leftpoint = 0번째, rightpoint = 인덱스 마지막 위치
    find = False  # 플래그는 Flase
    while lp <= rp : # lp가 rp랑 같을때 까지
        mid = (lp+rp) // 2 # 중간값 지정
        if num[mid] == i : #mid 와 찾으려는 숫자가 같을경우
            find = True  # 찾음을 표시
            print(1)   # 1을 출력
            break        # 찾았으니 루프에서 빠져나간다
        elif num[mid] < i : # 만약에 mid값이 찾으려는 숫자보다 작을경우
            lp = mid +1     # lp를 mid 보다 앞에서 찾는다.
        else :              # 찾으려는 숫자가 mid 보다 작을경우
            rp = mid -1     # rp를 미드 절반으로 줄인다.
    if not find :           # 만약에 숫자를 원소배열안에 찾으려는 숫자가 없을경우
      print(0)              # 0을 출력