[백준-python] 10815 숫자카드

알고리즘 분류

이진탐색 문제
https://www.fun-coding.org/Chapter16-binarysearch.html

첫 번째 시도

시간초과

#coding:utf8
# 숫자 카드
# 이진 탐색

from sys import stdin

N = int(stdin.readline())
NCards = sorted(map(int, stdin.readline().split()))
M = int(stdin.readline())
MList = map(int, stdin.readline().split())

def binary_search(searchList, target):
    if len(searchList) == 0:
        return 0
    if len(searchList) == 1:
        if searchList[0] == target:
            return 1
        else:
            return 0
    mid = len(searchList) / 2
    if searchList[mid] == target:
        return 1
    if target > searchList[mid]:
        return binary_search(searchList[mid:], target)
    else:
        return binary_search(searchList[:mid], target)

for m in MList:
    print(binary_search(NCards, m))

최종 정답

#coding:utf8
# 숫자 카드
# 이진 탐색

from sys import stdin

N = int(stdin.readline())
NCards = sorted(map(int, stdin.readline().split()))
M = int(stdin.readline())
MList = map(int, stdin.readline().split())

def binary_search(searchList, target, startIndex, endIndex):
    if startIndex > endIndex:
        return 0

    mid = (startIndex + endIndex) / 2
    if searchList[mid] == target:
        return 1
    if target > searchList[mid]:
        return binary_search(searchList, target, mid+1, endIndex)
    else:
        return binary_search(searchList, target, startIndex, mid-1)

for m in MList:
    startIndex = 0
    endIndex = len(NCards) -1
    print(binary_search(NCards, m, startIndex, endIndex))