이진 탐색

이진 탐색

반으로 쪼개면서 탐색하기
배열 내부의 데이터가 정렬되어 있어야만 사용 가능
시간복잡도 : O(logN)

1. 정렬된 리스트에서 시작점(0), 끝점(n), 중간점(n//2)을 이용한다.
2. 찾으려는 데이터와 중간점의 데이터를 비교한다.
3. 찾는 데이터가 중간점의 데이터보다 작으면 끝점을 중간점-1, 크면 시작점을 중간점+1 로 이동한다.
4. 찾는 데이터와 중간점의 데이터가 같을 때까지 반복한다.

array = [0, 2, 3, 4, 6, 9, 10]

target = 10

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start+end) // 2
        if array[mid] == target:
            return mid       
        if array[mid] > target:
            end = mid - 1  
        else:
            start = mid + 1
    return None    

result = binary_search(array, target, 0, len(array)-1)
if result == None:   
    print("원소가 존재하지 않습니다.")
else:
    print(result)

예제

오늘은 떡볶이 떡을 만드는 날이다. 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

처음봤을 때 이진탐색 문제인지를 바로 인지하지 못했는데 전형적인 이진 탐색 문제라고 한다.

탐색 범위가 1부터 10억까지의 정수인데, 10억과 같은 큰 수를 보면 이진 탐색을 떠올려야 한다.

파라메트릭 서치 : 최적화 문제를 결정 문제로 바꿔 해결하는 기법
최적화 : 범위 내에서 조건을 만족하는 가장 알맞은 값을 찾는 문제
결정 : 예, 아니오로 답하는 문제

범위 내에서 조건을 만족하는 가장 큰 값을 찾아라 (최적화)
-> 현재 이 높이로 자르면 조건을 만족할 수 있는가? (결정)

이진 탐색을 통해 범위를 반으로 쪼개가면서 알맞은 떡의 길이를 찾는다. 높이의 최댓값을 찾아야 하므로 떡의 길이의 합이 필요한 떡의 길이보다 길거나 같을 때마다 갱신시켜준다.

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

cakes = list(map(int, input().split()))
cakes.sort()


def binary_search(array, start, end):
    result = 0
    while start <= end:
        mid = (start + end) // 2
        total_len = sum([i-mid for i in cakes if i-mid > 0])        
        if total_len >= m:
            result = mid
            start = mid + 1        
        else:
            end = mid - 1

    return result


print(binary_search(cakes, 0, cakes[-1]))
    

# 4 6
# 19 15 10 17