백준 / 1920번 / 수찾기 (이진탐색)

📚문제

📝풀이

# 1920번 수 찾기
import sys
input = sys.stdin.readline

size = int(input())
info_list = list(map(int,input().strip().split()))
search = int(input())
find_list = list(map(int,input().strip().split()))

# 값을 찾을 리스트 (n_list) 정렬
info_list.sort()

# n : 찾을 수 ( find_list 의 원소 )
# info_list : 찾을 리스트 
def binary_search(n, info_list, start, finish):
    if start > finish: 
        return 0
    mid = (finish + start)//2
    if info_list[mid]==n:
        return 1
    elif info_list[mid]>n:
        return binary_search(n,info_list,start,mid-1)
    else:
        return binary_search(n,info_list,mid+1,finish)
    
for num in find_list:
    print(binary_search(num, info_list,0,size-1))

 

그냥 찾을 숫자를 .count() 등의 함수로 찾으면 시간초과가 뜬다

 

따라서 시간복잡도를 고려하여서 이진탐색의 방법을 사용해야한다

이진탐색의 시행횟수는

데이터가 N개 ->  log2(N) (=시행횟수 K)

시간복잡도(Big-O표기법) -> Olog(N) (= 상수부분 무시)

 

 

따라서

"자료의 갯수 N에 따른  이진탐색의 시행횟수는 log2(N)이며 시간 복잡도는 Olog(N)이다"

 

이진 탐색과 이진탐색의 시간복잡도에 대해서 정말 깔끔하고 알기 쉽게 설명해주신 분이 있어서 참고하였다

 

참고링크 출처 : 이진 탐색과 시간 복잡도 분석 (Binary Search and its Time Complexity Analysis) (tistory.com)