[백준] [Python] 1920번_수 찾기

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

1920번: 수 찾기

풀이

# 백준 1920번 문제 - 수 찾기
def binary_search(element, some_list, start = 0, end=None):
    if end == None:
        end = len(some_list) - 1
    
    if start > end:
        return 0
    
    mid = (start + end) // 2
    if element == some_list[mid]:
        return 1
    elif element < some_list[mid]:
        end = mid - 1
    elif element > some_list[mid]:
        start = mid + 1
    return binary_search(element, some_list, start, end)

n = int(input())
n_list = list(map(int, input().split(' ')))
n_list.sort()

m = int(input())
m_list = list(map(int, input().split(' ')))

for i in range(len(m_list)):
    print(binary_search(m_list[i], n_list))

이진 탐색을 통해 문제 해결

 

n 의 범위가 100,000 이기 때문에 in 을 사용하여 문제를 풀게 되면 시간초과가 나게 된다.