binary search:トッポッキ作り

問題の定義
今日東彬は旅行に行く両親の代わりにお菓子屋の仕事をすることにしました.今日はトッポッキ作りの日です
東彬家の打餅条が面白いのは打餅条の長さが固定されていないことです反対に、一袋入れた餅の全長をカッターで切って合わせます.カッターの高さ(H)を指定すると、一度に1列のケーキをカットします.高さがHより大きい餅は、Hの上の部分が切り落とされ、低い餅は切り落とされません.たとえば、高さ19、14、10、17 cmの餅を並べて、カッターの高さ15 cmを指定すると、カッターの高さは15、14、10、15 cmになります.切り餅の長さは4、0、0、2 cmの順です.お客様は6センチの長さを持って行きます.
お客様が来たときに要求される全長がMであれば、少なくともMのお菓子を得るために、カッターが設定できる最高高さ値を求めるプログラムを作成してください.

入力条件

行目は、打餅条数Nと、要求された打餅条長Mとを与える.(1 <= N <= 1,000,000, 1 <= M <= 2,000,000,000)

行目は、菓子の各高さを与える.餅の高さの総和はいつもM以上で、お客様は餅をいくらでも買うことができます.高さは10億の整数または0以下です.

しゅつりょくじょうけん
少なくともmの餅を家に持ち帰るために、カッターで設定できる最高高さ値を出力します.
I/O例

# 입력
4 6
19 15 10 17
# 출력
15

私が作ったコード

def binary_search(array, start, end, target):
	if start > end:
    	return None
    # 떡을 자를 지점(제일 긴 떡 기준 절반)
    mid = (start+end) // 2
    # 잘랐을 때 떡의 양을 저장할 변수
    hat = 0
    # 잘랐을 때 떡의 양 계산
    for i in range(len(array)):
        temp = array[i] - mid
        if temp > 0:
            hat += temp
    # 떡의 양이 충분한 경우 덜자르기
    if hat > target: # to the right
        return binary_search(array, mid, end, target)
    # 떡의 양이 부족한 경우 더자르기
    elif hat < target: # to the left
        return binary_search(array, start, mid, target)
    # 떡의 양과 요청한 떡의 길이가 동일할 때 정답처리
    else:
        return mid

# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력
n, target = list(map(int, input().split(" ")))

# 각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))

array = [19, 15, 10, 17]
start = 0
end = max(array)
target = 6
result = binary_search(array, start, end, target)
print(result)

正しいコード

# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력
n, target = 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)
    # 떡의 양이 부족한 경우 더 많이 자르기 (to the left)
    if total < target:
        end = mid - 1
    # 떡의 양이 충분한 경우 덜 자르기 (to the right)
    else:
        result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
        start = mid + 1
print(result)

考察する

再貴関数で表現したいです.ただし、正しい値がない場合はNoneが生成されます.最近の値を保存する場合は、グローバル変数を使用するのが最善の方法です.

バイナリナビゲーションでは、左または右に移動するときにstart~mid、mid~endを記述し、start~mid-1、mid+1~endを記憶する.この問題では結果は同じであるが,電子であればmid−midは0であり,これは意味のない演算である.

reference : https://github.com/ndb796/python-for-coding-test