二分探索をトレース表で解く｜配列の添字とループ条件を確認

二分探索は、整列済みの配列の中央と目的の値を比べ、探す範囲を半分ずつ狭める方法です。科目Bの擬似言語では、考え方を知っていても添字を一つ間違えると答えが変わります。

まず探索範囲を明確にする

配列[2, 5, 9, 12, 18, 21, 27]の添字を0～6とします。探索範囲の左端をlow＝0、右端をhigh＝6とし、mid＝⌊(low＋high)÷2⌋を求めます。ここでは両端を含む範囲[low, high]を使います。

18を探すトレース

• 1回目：low＝0、high＝6、mid＝3。値12は18より小さいのでlow＝4。

• 2回目：low＝4、high＝6、mid＝5。値21は18より大きいのでhigh＝4。

• 3回目：low＝4、high＝4、mid＝4。値18と一致し、添字4を返す。

中央の値より目的の値が大きければmid以下を捨て、小さければmid以上を捨てます。更新をlow＝midやhigh＝midにすると、範囲が縮まらず繰り返す場合があるため、mid＋1とmid－1を使います。

終了条件と前提

low≦highの間だけ繰り返し、low＞highになれば「見つからない」と判断します。配列が昇順に整列していることが前提です。未整列の配列にそのまま使うと、比較結果による範囲の切り捨てが正しくありません。

各回で候補をおよそ半分にするため、比較回数は要素数nに対してO(log n)です。同じ値が複数あると、通常の二分探索で最初に見つけた位置が必ず先頭とは限りません。先頭位置が必要なら、左側にも同じ値がないか調べる処理が必要です。

確認問題

同じ配列で値7を探すとどうなりますか。mid＝3の12で左側へ、mid＝1の5で右側へ、mid＝2の9で左側へ進み、low＝2、high＝1となります。low＞highなので「見つからない」が答えです。

出題範囲の確認：IPA公式の試験情報