二分探索チェックリスト

https://gyazo.com/3adb1ed9f7f843ada150d675bffb61a3

1: f(x)は正しいか？

ここが間違ってるとどうしようもない

何パターンか書き出してみて確認するべき

2: 大小比較は等号を含むか？

一致する値がない時に左右どちらを選ぶかによって変わる

https://gyazo.com/f387019b4af042257419dac27b4a501d

一致する場合にはそれ、しない場合には左を選ぶならf(x)=Tとf(x)<Tがleftになるように探索した上でleftを返す必要がある

1と2が分けられないタイプの問題もある

その場合は1がboolを返す実装になる

3: leftの初期値は適切か？

初期値がleftの満たすべき不等号を満たしているか2を踏まえて確認

4: rightの初期値は適切か？

code:python

def 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 right