昇順に整列されたn個のデータが格納されている配列Aがある。
流れ図は、2分探索法を用いて配列Aからデータxを探し出す処理を表している。
a、bに入る操作の正しい組合せはどれか。
ここで、除算の結果は小数点以下が切り捨てられる。
| a | b | |
| ア | k +1 → hi | k -1 → lo |
| イ | k -1 → hi | k +1 → lo |
| ウ | k +1 → lo | k -1 → hi |
| エ | k -1 → lo | k +1 → hi |
答え ウ
【解説】
aの処理は、データ列の真ん中のデータのA(k )が探しているデータx より小さいので、次の探索はデータ列の後半分になるので、k +1 → lo になる。
bの処理は、データ列の真ん中のデータのA(k )が探しているデータx より大きいので、次の探索はデータ列の前半分になるので、k -1 → hi になる。
【キーワード】
・2分探索法
- 2分探索法
2分探索法は昇順(降順)に整列されたデータの中から、目的のデータを探索するのに使用される方法である。
昇順に整列されたデータ場合の手順は- 整列されたデータ列の真ん中のデータと探すデータを比較する。
- 真ん中のデータが、探しているデータより大きい場合は、データ列の前半分に対し、上の手続きを行う。
- 真ん中のデータが、探しているデータより小さい場合は、データ列の後半分に対し、上の手続きを行う。
- 等しかったら、探すデータがあったので終了。
- 探す範囲がなくなったら、探すデータがなかったので終了。
もっと、「2分探索法」について調べてみよう。
戻る
一覧へ
次へ