-
masashinakata
- 5792
- 1
- 2
- 0
-
- いいね！0
普通のC++使い、銀天すばる
@SubaruG
STLの名前付けが悪いのは本当にアレ． 「二分探索やりたいんだけど」って考えて素直に std::binary_search を調べたら「STL使えねーな」ってなるのも当然なのだ…
2014-07-19 21:09:53
みさわ
@Mi_Sawa
ちなみに, コイツは, res-l の値の2進表記での各桁を msb の方から求めているというアレで, 超わかりやすい.(個人の感想です) twitter.com/Mi_Sawa/status…
2014-07-19 21:13:15
みさわ
@Mi_Sawa
整数二分探索, int res=l; for(int d=(十分でかい2^n); d; d>>=1) if(res+d <= r && ok(res+d)) res += d; すると間違えない. (n回目)
2014-07-19 20:43:56
くりんぺっと
@climpet
std::set::findみたいに，「要素が含まれていればその要素へのイテレータを，含まれていなければendを返す」二分探索関数が標準であれば微妙に便利な気がするのだけど，存在しないので仕方なくlower_boundのあと自分でチェックする羽目になって微妙に面倒
2014-07-19 21:15:35
Япон Бүресе🏴☠️
@southerwolfie
整数で二分探索するときはl,rを解の範囲の少し外側においてwhile(l+1<r)にしてl=Mかr=Mを使い、最小値を求めたいときはr、最大値を求めたいときはlを答えるようにしている
2014-07-19 21:19:16
ぱ
@purple_jwl
そういえば二分探索で mid = (left + right) >> 1 って書く人わりといるみたいだけど、これは好みの違いなのかな(?)
2014-07-20 14:57:57
koba
@kobae964
競技プログラミング歴2年くらいなのに簡単な2分探索さえ満足に書けない私 pic.twitter.com/dk35eg23wF
2014-10-27 01:54:01
拡大
みさわ
@Mi_Sawa
何度でも言うけど, 整数二分探索, よくバグらせていたのが, for(int d = 1<<20; d; d>>=1) if(res+d<n && ok(res+d)) res += d; のような書き方にしてからバグらせる率がかなり下がった.
2014-10-27 01:56:02
Япон Бүресе🏴☠️
@southerwolfie
整数二分探索はwhile(L+1<R)にして最小値が知りたいときはRが答えで最大値が知りたいときはLが答えというふうにしている
2014-10-27 01:57:04
Hideyuki Tanaka
@tanakh
いつも while(hi-lo>1) { mi=(hi+lo)/2; if(ok(mi)) lo=mi; else hi=mi; } みたいな感じだなあ。ifのelseとかが無いところがミスりにくいんだろうか。
2014-10-27 01:58:26
とーらす🌸📦🌕✨🍀
@torus711
整数にぶたん、int lb = min, ub = max; while( lb+1 < ub ){ int mid = ( lb+ub )/2; ( c( mid ) ? lb : ub ) = mid; } 派。lb, ub のどっちが c を満たすのかを意識して更新する
2014-10-27 01:59:53