동빈나 2021 이코테_5. 이진 탐색

• 순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기위해 앞에서부터 하나씩 확인
• 이진탐색 : 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터 탐색 ( 시작점, 끝점, 중간점을 이용하여 탐색범위를 설정한다.)

단계마다 절반씩 줄어드는 알고리즘의 시간복잡도는 보통 로그N

 <예제문제1>

내코드 _ 잘못됨 ( 완전탐색이므로 시간초과남 )

n,m = map(int, input().split())

input_list = list(map(int, input().split()))

for i in range(max(input_list), 0, -1):
    count = 0
    for j in input_list:
        count += max(0, j-i)
    if count >= m:
        print(i)
        break

내코드2 _ 이진탐색으로 다시 풀어봄

import sys
sys.setrecursionlimit(10**6)

n,m = map(int, input().split())

input_list = list(map(int, input().split()))

end = max(input_list)
start = 0
count  = 0
result = []

def binary_search(input_list, start, end):
    if start > end:
        return None
    count = 0
    mid = start + end //2
    for j in input_list:
        count += max(0, j-mid)
    if count >= m: #잘린떡이 충분한경우
        result.append(count)
        return binary_search(input_list, mid+1, end)
    else: # 잘린떡이 모자란경우 ( 더 짧게 잘라야함)
        return binary_search(input_list, start, end-1)

binary_search(input_list, start, end)
print(result[-1])

매우 큰 탐색범위를 보면 먼저 이진탐색을 떠올려야함

 

동빈나님 코드

< 예제문제2 _ 정렬된 배열에서 특정수의 개수 구하기 >

처음 전체탐색 범위에 대해서 이진탐색을 두번 수행하여 1번 이진탐색은 첫번째위치, 2번 이진탐색은 마지막위치를 찾아서 두 위치간 차이를 구하면 됨

 

실제 이진탐색 코드를 직접 작성해서 풀수도 있고,  표준라이브러리로도 구현할 수 있다.

 

동빈나님 코드: (표준라이브러리사용)

#count_by_range()는 여러 코딩테스트에서 유용하게 사용될수 있으므로 팁노트에 저장하여 사용해놓으면 좋음