1920번 수 찾기

Posted on In , ,

문제정의

이분 탐색을 이용한 수 탐색 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def binary_search(A, key):
    l = 0
    r = len(A)

    while l < r:
        mid = (l+r) // 2
        if A[mid] == key:
            return 1
        elif A[mid] > key:
            r = mid
        else:
            l = mid+1

    return 0

N = int(input())

A = input().split(" ")

for i, _ in enumerate(A):
    A[i] = int(A[i])

A.sort()

M = int(input())

X = input().split(" ")

for i, _ in enumerate(X):
    print(binary_search(A, int(X[i])))

이분 탐색을 구현하는 문제이다. 입력을 받는 부분을 건너 뛰고 binary_search함수를 보면 된다. 인덱스를 기준으로 이분탐색을 진행한다.

테스트


테스트 화면