問題設定
整数二分探索とは，以下の矢印の位置を求める問題である。
パターン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) = mid;と更新する。
失敗パターンとして，[lb, ub) として範囲を扱った場合を考える。この間違いが非常に多い
[lb, ub) の中にcheckがTrueになるものが無くなってしまった。
ダメってはっきりわかんだね。
おすすめの方法
@kinaba 自分は整数の二分探索は全部このやり方で書いています。http://t.co/KV1g6rH3 。個人的に間違いが少なくて良い書き方かなと思っていて、他の人の意見に興味あります。
— hirosegolf (@hirose_golf) 2012年7月3日
