[#1920] 수 찾기

문제

#1920 수 찾기
Silver4
적용 알고리즘: 이분탐색 알고리즘

---

풀이 방법

• 이분탐색 알고리즘을 사용하여 탐색한다.
• 이분탐색을 수행하기 위해서는 배열이 정렬되어 있어야 한다.
• M은 입력받은 순서대로 존재 여부를 판단해야 하기 때문에 A만 sort하고, M원소 하나씩 A에 이분탐색으로 탐색한다.

코드 흐름

1. 값을 사용자에게서 입력받는다.
2. 이분탐색을 수행해야 하는 배열(A)만 정렬한다.
3. M의 각 원소에 대해서 이분탐색을 진행한다.

코드

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while (low <= high):
        mid = (low + high) // 2
        if (arr[mid] == target):
            return 1
        elif (arr[mid] > target):
            high = mid - 1
        else:
            low = mid + 1
    return 0


n = int(input())
A = [int(m) for m in input().split()]
m = int(input())
M = [int(m) for m in input().split()]

A.sort()

for i in range(len(M)):
    print(binary_search(A, M[i]))

체감 난이도: 3.7/5
솔직히 이 문제도 알고리즘을 이분탐색이라고 미리 알고 있지 않았으면 이분탐색을 썼을까 싶다. 아마 일반 탐색 방법을 사용했다가 백준에서 시간초과가 났다면 이분탐색을 썼을까 싶다.