#27 [파이썬] 백준 1920번: 수 찾기

<문제>

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

---

 

<소스코드>

import sys
input = sys.stdin.readline

n = int(input())
n_lst = list(map(int, input().split()))
m = int(input())
m_lst = list(map(int, input().split()))

n_lst.sort()


def binary_search(n_lst, i, start, end):
    while start <= end:
        mid = (start + end) // 2
        if n_lst[mid] == i:
            return True
        elif n_lst[mid] > i:
            end = mid - 1
        else:
            start = mid + 1
    return False


for i in m_lst:
    if binary_search(n_lst, i, 0, n - 1):
        print(1)
    else:
        print(0)

---

 

<NOTE>

아래 과정을 통해 이분탐색을 할 수 있다.

 

1. 탐색할 배열을 오름차순으로 정렬한다.

2. 탐색할 배열, 그 배열의 시작점과 끝점, 찾아야할 숫자를 이용한다.

3. 탐색할 배열의 중간의 원소를 찾아야 할 숫자와 비교하여, 찾아야할 숫자가 더 크면 시작점을 중간의 원소 + 1로 옮기고 찾아야할 숫자가 더 작으면 끝점을 중간의 원소 - 1로 옮긴다.

4. 중간의 원소와 찾아야할 숫자가 서로 같으면 찾은 것이고, while문을 빠져나올 때까지 찾지 못하면 없는 것이다.

5. 시작점이 끝점보다 작으면 위의 3~4 과정을 반복한다.