二分探索チェックリスト
二分探索の四つの構成要素をチェックする
1: f(x)は正しいか？
ここが間違ってるとどうしようもない
何パターンか書き出してみて確認するべき
2: 大小比較は等号を含むか？
一致する値がない時に左右どちらを選ぶかによって変わる
一致する場合にはそれ、しない場合には左を選ぶならf(x)=Tとf(x)<Tがleftになるように探索した上でleftを返す必要がある
abc174Eでは逆に右を返す必要があった
1と2が分けられないタイプの問題もある
その場合は1がboolを返す実装になる
3: leftの初期値は適切か？
初期値がleftの満たすべき不等号を満たしているか2を踏まえて確認
4: rightの初期値は適切か？
pythondef solve(N, K, AS):
left = 0 # (3)
right = max(AS) # (4)
while left < right - 1:
x = (left + right) // 2
y = f(x) # (1)
if y > K: # (2)
left = x
else:
right = x
return rightRelated Pages
- →atcoder×abc168×abc169×abc170×abc171×abc172×abc173×ABC174×abc175×abc176×abc177×abc178×abc179×abc180×abc181×abc182×abc183→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]