[Codility] 14. Binary search algorithm (MinMaxDivision)

Binary search algorithm

#O(logn)
def binarySearch(A,x):
    n = len(A)
    beg = 0
    end = n - 1
    result = -1
    while (beg <= end):
        mid = (beg + end) / 2
        if (A[mid] <= x):
            beg = mid + 1
            result = mid
        else:
            end = mid - 1
    return result

14.1 MinMaxDivision

초기화

1. Lower Bound - 모든 원소 sum
2. Upper Bound - max(A)

def is_valid(A, K, max_sum):
    # 배열 A를 K개의 블록으로 나눌 때, 블록의 합이 max_sum 이하인지 확인
    block_sum = 0
    block_count = 0

    for element in A:
        block_sum += element
        if block_sum > max_sum:
            # 새로운 블록 시작
            block_sum = element
            block_count += 1

    # 나눈 블록의 수와 K 비교
    return block_count + 1 <= K


def solution(K, M, A):
    min_val = max(A) #Lower Bound
    max_val = sum(A) #Upper Bound

    while min_val <= max_val:
        mid = (min_val + max_val) // 2

        if is_valid(A, K, mid):
            max_val = mid - 1
        else:
            min_val = mid + 1

    return min_val