<파라메트릭 서치> 7-8

파라메트릭 서치: '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'-> 이진 탐색을 이용해 해결-> 이진 탐색을 재귀적으로 구현하지 않고 반복문을 이용해 구현하면 더 간결하게 문제를 풀 수 있음

 

n, m=list(map(int, input().split(' ')))
array=list(map(int, input().split()))

start=0
end=max(array)

result=0
while(start<=end):
    total=0
    mid=(start+end)//2
    for x in array:
        if x>mid:
            total+=x-mid
    if total<m:
        end=mid-1
    else:
        result=mid
        start=mid+1
print(result)