파이썬 백준 1920 수 찾기

def Bsearch(list, target, start, end) :     if start > end :         return 0     center = (start + end) // 2     if target == list[center] :         return 1     if target < list[center] :         return Bsearch(list, target, start, center - 1)     if target > list[center] :         return Bsearch(list, target, center + 1, end) n = int(input()) unsortedA = list(map(int, input().split())) m = int(input()) mlist = list(map(int, input().split())) A = sorted(unsortedA) n = len(A) - 1 for i in mlist :     print(Bsearch(A, i, 0, n))

태그에 이분 탐색이 있어서 이분 탐색이 뭔지 공부하고 구현했다.

처음에는 list[center :]와 list[: center]로 갈라져서 재귀하는 방식으로 구현했는데,

list와 target의 2개 변수만 받는 함수라 구현하기 쉬웠지만 백준에 제출하니 시간초과가 떴다.

 

검색해보니 [:]로 슬라이스 하는 연산이 자른 리스트의 길이만큼의 시간복잡도를 가진다고 한다.

센터에서 자르면 for문 하나 돌리는 시간의 반을 쓰니, 이분탐색을 구현하고도 단순탐색급의 시간을 쓴 셈이다.

 

[:]로 잘린 list를 재귀함수에 넣는 방식 대신start와 end라는 새 변수를 같이 입력해서

재귀할때 같은 list를 넣되 start와 end 값이 달라지도록 하니 시간 안에 계산을 마쳤다.