探索アルゴリズムの試験問題への適用
探索の本番問題では比較回数やlow/high/midの変化を追う。二分探索は中央値との比較結果で、探索範囲からmidを除外して更新する。
この単元で学ぶこと
- 初期範囲の意味と役割を説明できる
- 中央比較の意味と役割を説明できる
- 右半分更新の意味と役割を説明できる
- 二分探索のlow/high/midを反復ごとに追い比較回数を求められる
本文解説
0始まり配列ならlow=0、high=n-1から始める例が多い。mid=(low+high) div 2のような仕様に従い、targetが大きければlow=mid+1、小さければhigh=mid-1とする。
初期範囲 探索開始時のlow/high。 0始まりなら0とn-1が典型。
中央比較 a[mid]とtargetを比較する処理。 一致なら終了。
右半分更新 target>a[mid]ならlowをmid+1へ更新する。 midは既に不一致なので除外する。
左半分更新 target<a[mid]ならhighをmid-1へ更新する。 midを除外する。
比較回数 target発見または範囲消滅までの中央比較回数。 各反復1回ずつ数える。
各反復でlow,high→mid→a[mid]→更新後low/highを書き出す。
[2,4,6,8,10,12,14]で12を探す。mid=3(8)→右へ、mid=5(12)で2回目に発見。
図解
重要ポイント
- 初期範囲: 探索開始時のlow/high。
- 中央比較: a[mid]とtargetを比較する処理。
- 右半分更新: target>a[mid]ならlowをmid+1へ更新する。
- 左半分更新: target<a[mid]ならhighをmid-1へ更新する。
- midを比較済みなのに次範囲へ残すと無限ループや回数ずれにつながる。
間違えやすい点
- high=nではなくn-1か仕様を確認する。
- mid計算の丸め規則を無視しない。
- targetが大きいのにhighを下げない。
用語解説
- 初期範囲
- 探索開始時のlow/high。
- 中央比較
- a[mid]とtargetを比較する処理。
- 右半分更新
- target>a[mid]ならlowをmid+1へ更新する。
- 左半分更新
- target<a[mid]ならhighをmid-1へ更新する。
- 比較回数
- target発見または範囲消滅までの中央比較回数。
関連教材
参考資料
教材データに登録された参考リンクです。リンク先の内容や更新日は提供元でご確認ください。
確認問題の出題・採点や学習履歴の保存にはログインが必要です。