백준 1920. 수 찾기 [Python]

• 문제 : 수 찾기
• 난이도 : 실버 4
• 언어 : Python
• 문제 링크 : https://www.acmicpc.net/problem/1920

1920번: 수 찾기

import sys

def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start+end) // 2

        if data[mid] == target:
            return 1
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return 0



N = sys.stdin.readline()
check = list(map(int, sys.stdin.readline().split()))
M = sys.stdin.readline()
num = list(map(int, sys.stdin.readline().split()))
check.sort()
for i in num:
    print(binary_search(i, check))

처음엔 입력의 범위를 자세히 안보고 풀이를 진행했다가 시간초과가 난 문제.

for를 통한 반복으로 찾으면 시간초과가 나므로 이진탐색으로 탐색을 진행해야한다.

이진탐색은 정렬된 리스트로 진행해야 하므로 함수를 진행하기전에 리스트를 정렬시키고 함수를 진행.