[이코테] 이진탐색 실전문제 2번 풀이

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(1000000)
def midsort(array,start,end,target):
    if start > end:
        return 0
    mid = (start+end) // 2
    if target < array[mid]:
        return midsort(array,start,mid-1,target)
    elif target > array[mid]:
        return midsort(array,mid+1,end,target)
    elif target == array[mid]:
        return 1
    


N = int(sys.stdin.readline())
array = list(map(int,sys.stdin.readline().split()))
array.sort()
M = int(sys.stdin.readline())
target = list(map(int,sys.stdin.readline().split()))

for i in range(M):
    bool = midsort(array,0,N-1,target[i])
    if bool == 1:
        print("YES")
    else:
        print("NO")

재귀함수를 사용하다보니 반드시 start > end라면 return으로 함수를 끝내줘야 한다 .

안그러면 무한한 재귀가 돌아가게 되므로

일단 array.sort()를 해줘야 하는데

저 파이썬 내장함수 sort()가 퀵정렬을 통해 정렬하므로 원소의 개수가 N개라면 O(NlogN)만큼 소요된다

또 이진탐색이 찾아야하는 원소를 절반씩 줄여주므로 O(logN),이것을 M번 수행해야 하므로 총 소요시간은 O(MlogN)

총 소요시간 : O((M+N)logN) 이 소요되었다.

또 문법에서 데이터의 크기가 너무 커지면 input 함수에서 감당할 수 없는 경우가 종종 나오는데,

이를 방지하기 위하여 sys.stdin.readline()을 통해 입력을 받아줘야 한다.

 

또 잘 까먹는 입력 예시

 

0 1 2 5 6

이 배열에 순서대로 저장되게 하고 싶다면

array = list(map(int,sys.stdin.readline().split()) 

split() 자체가 공백을 기점으로 구분이다. 공백 기점으로 배열에 원소 하나씩 저장시킬 것