- 1: f(x)は正しいか？
- ここが間違ってるとどうしようもない
- 何パターンか書き出してみて確認するべき
- 2: 大小比較は等号を含むか？
- 一致する値がない時に左右どちらを選ぶかによって変わる
- 一致する場合にはそれ、しない場合には左を選ぶならf(x)=Tとf(x)<Tがleftになるように探索した上でleftを返す必要がある
- abc174Eでは逆に右を返す必要があった
- 1と2が分けられないタイプの問題もある
- その場合は1がboolを返す実装になる
- 3: leftの初期値は適切か？
- 初期値がleftの満たすべき不等号を満たしているか2を踏まえて確認
- 4: rightの初期値は適切か？
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