問題設定 整数二分探索とは,以下の矢印の位置を求める問題である。 パターンA パターンB 解き方 前提として,範囲を閉区間で扱うと微妙にバグるので半開区間で扱う。while文の条件はどちらのパターンでも ub - lb > 1 である。 パターンA [lb, ub) として範囲を扱うのが正解。 mid = (lb + ub) / 2とする。矢印のところをチェックして(check(mid) ? lb : ub) = mid;と更新する。 失敗パターンとして,(lb,ub] として範囲を扱った場合を考える。 (lb, ub] の中にcheckがTrueになるものが無くなってしまった。 ダメってはっきりわかんだね。 パターンB (lb, ub] として範囲を扱うのが正解。 mid = (lb + ub) / 2とする。矢印のところをチェックして(check(mid) ? ub : lb) = m