二分探索をバグらせないための考え方

問題設定

整数二分探索とは,以下の矢印の位置を求める問題である。

パターンA

f:id:kujira16:20150926234308p:plain

パターンB

f:id:kujira16:20150926234314p:plain

解き方

前提として,範囲を閉区間で扱うと微妙にバグるので半開区間で扱う。while文の条件はどちらのパターンでも ub - lb > 1 である。

パターンA

[lb, ub) として範囲を扱うのが正解。

f:id:kujira16:20150927000112p:plain

mid = (lb + ub) / 2とする。矢印のところをチェックして(check(mid) ? lb : ub) = mid;と更新する。

f:id:kujira16:20150927000127p:plain

失敗パターンとして,(lb,ub] として範囲を扱った場合を考える。

f:id:kujira16:20150927001531p:plain

(lb, ub] の中にcheckがTrueになるものが無くなってしまった。

ダメってはっきりわかんだね。

パターンB

(lb, ub] として範囲を扱うのが正解。

f:id:kujira16:20150927001626p:plain

mid = (lb + ub) / 2とする。矢印のところをチェックして(check(mid) ? ub : lb) = mid;と更新する。

f:id:kujira16:20150927001641p:plain

失敗パターンとして,[lb, ub) として範囲を扱った場合を考える。この間違いが非常に多い

f:id:kujira16:20150927001721p:plain

[lb, ub) の中にcheckがTrueになるものが無くなってしまった。

ダメってはっきりわかんだね。

おすすめの方法

資料

この記事は以下の記事で言及されています

konjo-p.hatenablog.com