にぶたん談義

ぱ @purple_jwl

二分探索書くとき、ループ抜ける判定が怪しくて無限ループになることある

ぱ @purple_jwl

前回のこどふぉD解いてて思った（

ぱ @purple_jwl

クソ雑魚すぎる

みさわ @Mi_Sawa

整数二分探索, int res=l; for(int d=(十分でかい2^n); d; d>>=1) if(res+d <= r && ok(res+d)) res += d; すると間違えない. (n回目)

みさわ @Mi_Sawa

int m = (l+r)/2 とかする書き方, ぼくも苦手だ.

ぱ @purple_jwl

二分探索はできればｎ回ループで終わらせたい（切実

くりんぺっと @climpet

二分探索，境界あたりの条件がよく分からなくなるので苦手

とーらす🌸📦🌕✨🍀 @torus711

ub, lb をもつ整数二分探索、lb と ub のどっちが condition を満たすのか意識しておくとちょっとよさげ。そうすると素直に ( ok( mid ) ? lb : ub ) = mid と書ける。ループは while ( lb + 1 < ub )

ぱ @purple_jwl

競プロ関連のツイート、自分がすればするほど雑魚なのがバレてしまうのでつらい

くりんぺっと @climpet

二分探索を二分間行う

よすぽ @yosupot

[l,r)で考えればあんま間違えないと思うけどなぁ

くりんぺっと @climpet

ついでに，二分探索と二分法はよく混同する

みさわ @Mi_Sawa

(l+r)/2 の切り捨てが死ぬみたいな何かがある事は覚えていて, 何がどうなんだっけと思い出すのが面倒くさい.

わふならず @wfnarazu

いわゆる繰り返し二乗法では2ベキ作ってく方が好きなんだけど，整数の二分探索は (l+r)/2 するなあ，[l,r) もしくは (l,r] が不変条件になってたら間違えようがない．

わふならず @wfnarazu

@Mi_Sawa 一方が負だとアレかもしれない？

みさわ @Mi_Sawa

@stac_task あぁ, そんなのも…

くりんぺっと @climpet

あんまりそういう問題見たことはないけど，もし二分探索的なことを負の数を含む区間について行おうとした場合，[l,r) なら問題ないはずだけど， [l,r] だと除算の切り捨て方向の問題で死ぬ場合があるので注意

ぱ @purple_jwl

(さぁ己の持つ二分探索に関する知識を放出するのじゃ...)

hirokazu @hirokazu1020

二分探索と二分法の違いよくわかってないけど区別する意味がわからない

フキーニョ @fuqinho

二分探索で無限ループはあんまり無いけど、ダイクストラとかでキューからpopするの忘れて無限ループは儀式のようにほぼ毎回やる

Тагсанов @tagsanov

ALESSで二分探索の説明するときはub,lb,mdとしました

Masaki Hara @qnighy

l,r,mにおける二分探索では、1次元領域を「A:条件を満たしている」「B:不明」「C:条件を満たしていない」の3区間に分割する。そのうえで、Aの最大元がl, Cの最小元がrという不変条件を保ちつつ、(r-l)が指数的に1まで減少するループを書けばよい。

Masaki Hara @qnighy

@qnighy ある値以上の整数全体がwell-orderなのでループの停止性がわかり、特にその速度が指数的であることもわかる。

Masaki Hara @qnighy

@qnighy また、ループの脱出条件はr - l <= 1であるが、実はr - l >= 1という不変条件が保たれるので、脱出時にはr - l == 1が成立し、したがって「B:不明」という区間は脱出時に消滅していることがわかる。

くりんぺっと @climpet

std::binary_searchさんはどうしてboolしか返さないんだ…