問題 > 問 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, "番目にあります")

動かして確かめる

空欄をすべて選んで「あなたの答えで動かす」を押すと、1 行ずつ追えます。

次の値を当てよう(トレース当て)

正解のプログラムを動かしたとき、値はいくつになるでしょう。頭の中で追ってから答えて、そのあと動かして確かめましょう。

  1. 7 行目を 1 回目に実行したあと、naka は?
  2. 11 行目を 1 回目に実行したあと、hidari は?

つぎは