基本情報技術者試験の科目Bのサンプル問題を題材に，2分探索による検索処理について学習します。この問題では，2分探索のプログラムにある不具合によって，探索範囲が狭まらず無限ループになる場合を確認します。
（令和4年度12月公開） 基本情報技術者試験 サンプル問題 科目B 問13
問 次の記述中の に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。
関数 search は，引数 data で指定された配列に，引数 target で指定された値が含まれていればその要素番号を返し，含まれていなければ －1 を返す。data は昇順に整列されており，値に重複はない。
関数 search には不具合がある。例えば，data の 場合は，無限ループになる。
〔プログラム〕
○整数型: search(整数型の配列: data，整数型: target)
整数型: low，high，middle
low ← 1
high ← dataの要素数
while (low ≦ high)
middle ← (low ＋ high) ÷ 2 の商
if (data[middle] ＜ target)
low ← middle
elseif (data[middle] ＞ target)
high ← middle
else
return middle
endif
endwhile
return －1
解答群
ア 要素数が1で，targetがその要素の値と等しい
イ 要素数が2で，targetがdataの先頭要素の値と等しい
ウ 要素数が2で，targetがdataの末尾要素の値と等しい
エ 要素に－1が含まれている
【解答】ウ
【解説】
search は，整列済みの配列を2分探索する処理である。ただし，data[middle] ＜ target の場合に low ← middle としているため，探索範囲が狭まらない場合がある。例えば，要素数が2で，target が data の末尾要素の値と等しい場合を考える。low ＝ 1，high ＝ 2 なので，middle ＝ (1 ＋ 2) ÷ 2の商＝1 となる。data[1] ＜ target なので，low ← middle が実行されるが，middle が1なので，low は1のままで変化しない。その結果，low ＝ 1，high ＝ 2 の状態が繰り返され，middle も1のまま変化しない。したがって，探索範囲が狭まらず，whileの条件 low ≦ high が常に真となるため，無限ループになる。
※ このような無限ループを防ぐには，探索範囲が必ず狭くなるように low や high の値を更新する必要がある。例えば，data[middle] ＜ target の場合は，middle 自身は既に調べているので，low ← middle ＋ 1 とすれば，探索範囲を確実に狭めることができる。
【参考】
この問題のポイント
この問題から学べることは，
- 2分探索による検索方法
- 探索範囲をlowとhighで管理する方法
- 整数の割り算の商を使ってmiddleを求める方法
- 探索範囲が狭まらないことによって無限ループになる場合
- プログラムの不具合をトレースによって確認する方法
です。特に，2分探索では，条件に応じて low や high を更新し，探索範囲を必ず狭めていくことが重要です。値を更新しているように見えても，実際には同じ値のままになっていないか，トレースして確認しましょう。
基本情報技術者試験の学習におすすめの参考書
基本情報技術者試験の合格を目指す方におすすめの参考書です。
学習のお役に立ちましたら
この記事が少しでも学習のお役に立ちましたら，今後も分かりやすい解説や学習コンテンツを継続してお届けする励みになります。
よろしければ、このサイトを応援いただけますと嬉しいです。
※OFUSEは，クリエイターやコンテンツ制作を直接支援できるサービスです。
