問題 > 問 20
二分探索
探索むずかしさ ★★★
場面
小さい順に並んだ配列 Data から、入力した値を探します。真ん中の値と比べて、探す範囲を半分ずつにせばめていきます。この問題の「〜番目」は添字のことで、先頭を 0 番目と数えます。
【外部からの入力】には、次の値が順に入ります: 61(入力は例によって変えて試せます)
プログラム
空欄 ア・イ に入るものを選びましょう。
1 Data = [11, 23, 35, 47, 59, 61, 73, 85, 97]
2 mokuhyo =【外部からの入力】
3 hidari = 0
4 migi = 要素数(Data) - 1
5 mitsukatta = -1
6 hidari <= migi and mitsukatta == -1 の間繰り返す:
7 | naka = (hidari + migi) 2
8 | もし Data[naka] == mokuhyo ならば:
9 | | mitsukatta = naka
10 | そうでなくもし Data[naka] < mokuhyo ならば:
11 | | hidari =
12 | そうでなければ:
13 ⎿ ⎿ migi = naka - 1
14 もし mitsukatta == -1 ならば:
15 | 表示する(mokuhyo, "は見つかりません")
16 そうでなければ:
17 ⎿ 表示する(mokuhyo, "は", mitsukatta, "番目にあります")
解説
並んだ配列では、真ん中の値と比べるだけで、探す範囲を半分に減らせます。61 を探すと、naka は 4(59)→ 6(73)→ 5(61)と動き、3 回で見つかります。先頭から調べる探索なら 6 回かかります。真ん中の添字の求め方は、教科書によって、(hidari + migi) ÷ 2 と書いたり、切り上げて (hidari + migi + 1) ÷ 2 にしたりします。どれでも探索はできますが、調べる順番が少し変わります。
動かして確かめる
空欄をすべて選んで「あなたの答えで動かす」を押すと、1 行ずつ追えます。
次の値を当てよう(トレース当て)
正解のプログラムを動かしたとき、値はいくつになるでしょう。頭の中で追ってから答えて、そのあと動かして確かめましょう。
- 7 行目を 1 回目に実行したあと、naka は?
- 11 行目を 1 回目に実行したあと、hidari は?