kujira16 https://blog.hatena.ne.jp/kujira16/ くじらにっき++ https://kujira16.hateblo.jp/ アルゴリズム 問題設定 整数二分探索とは，以下の矢印の位置を求める問題である。 パターンA パターンB 解き方 前提として，範囲を閉区間で扱うと微妙にバグるので半開区間で扱う。while文の条件はどちらのパターンでも ub - lb > 1 である。 パターンA [lb, ub) として範囲を扱うのが正解。 mid = (lb + ub) / 2とする。矢印のところをチェックして(check(mid) ? lb : ub) = mid;と更新する。 失敗パターンとして，(lb,ub] として範囲を扱った場合を考える。 (lb, ub] の中にcheckがTrueになるものが無くなってしまった。 ダメってはっ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkujira16.hateblo.jp%2Fentry%2F2015%2F09%2F26%2F234614" title="2分探索のバグりにくい書き方 - くじらにっき++" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://cdn-ak.f.st-hatena.com/images/fotolife/k/kujira16/20150926/20150926234308.png Hatena Blog https://hatena.blog 2015-09-26 23:46:14 rich https://kujira16.hateblo.jp/entry/2015/09/26/234614 1.0 100%