[백준-python] 1920 수 찾기

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

첫 번째 시도

#coding:utf8
# 수 찾기

from sys import stdin

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

for m in MList:
    if m in NList:
        print(1)
    else:
        print(0)

중간 시도

#coding:utf8
# 수 찾기

from sys import stdin

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


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

    mid = len(searchList) // 2
    if target == searchList[mid]:
        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(NList, m))

최종 정답

#coding:utf8
# 수 찾기

from sys import stdin

N = int(stdin.readline())
NList = 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 target == searchList[mid]:
        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 = N-1
    print(binary_search(NList, m, startIndex, endIndex))