二分探索｜擬似言語のトレース解説と練習問題
関数 search は、昇順に並んだ配列 data から target を探し、見つかった要素番号を返す。見つからなければ 0 を返す。配列の要素番号は 1 から始まる。
プログラム
| 1 | ○整数型: search(整数型の配列: data, 整数型: target) |
| 2 | 整数型: low ← 1 |
| 3 | 整数型: high ← dataの要素数 |
| 4 | 整数型: middle |
| 5 | while (low ≦ high) |
| 6 | middle ← (low ＋ high) ÷ 2 の商 |
| 7 | if (data[middle] < target) |
| 8 | low ← middle ＋ 1 |
| 9 | elseif (data[middle] > target) |
| 10 | high ← middle － 1 |
| 11 | else |
| 12 | return middle |
| 13 | endif |
| 14 | endwhile |
| 15 | return 0 |
何をしているか
昇順に並んだ配列から、目的の値を探します。探す範囲の真ん中 middle と比べ、目的の値のほうが大きければ範囲の左端 low を、小さければ右端 high を動かして、範囲を半分にします。
トレースのコツ
- 表の列は
low、high、middle、data[middle]の4つにします。 middleは「(low ＋ high) ÷ 2 の商」です。割り切れないときは切り捨てます。- 範囲を動かすときは
middle ＋ 1かmiddle − 1です。middle自身はもう調べたので、範囲から外します。
よくある間違い
- 戻り値を、見つけた値で答える。返すのは要素番号です。
lowとhighのどちらを動かすかを逆にする。「data[middle] が目的の値より小さい → 目的の値は右側 → low を右へ」と声に出して確かめます。- 商の切り捨てを忘れ、四捨五入してしまう。
例題：search({2, 8, 14, 24, 29, 33}, 8) を最後まで追う
上のプログラムを search({2, 8, 14, 24, 29, 33}, 8) で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。
| # | 行 | したこと | data | target | low | high | middle |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 宣言 | {2, 8, 14, 24, 29, 33} | 8 | 1 | — | — |
| 2 | 3 | 宣言 | {2, 8, 14, 24, 29, 33} | 8 | 1 | 6 | — |
| 3 | 4 | 宣言 | {2, 8, 14, 24, 29, 33} | 8 | 1 | 6 | 未設定 |
| 4 | 5 | 条件判定（真） | {2, 8, 14, 24, 29, 33} | 8 | 1 | 6 | 未設定 |
| 5 | 6 | 代入 | {2, 8, 14, 24, 29, 33} | 8 | 1 | 6 | 3 |
| 6 | 7 | 条件判定（偽） | {2, 8, 14, 24, 29, 33} | 8 | 1 | 6 | 3 |
| 7 | 9 | 条件判定（真） | {2, 8, 14, 24, 29, 33} | 8 | 1 | 6 | 3 |
| 8 | 10 | 代入 | {2, 8, 14, 24, 29, 33} | 8 | 1 | 2 | 3 |
| 9 | 5 | 条件判定（真） | {2, 8, 14, 24, 29, 33} | 8 | 1 | 2 | 3 |
| 10 | 6 | 代入 | {2, 8, 14, 24, 29, 33} | 8 | 1 | 2 | 1 |
| 11 | 7 | 条件判定（真） | {2, 8, 14, 24, 29, 33} | 8 | 1 | 2 | 1 |
| 12 | 8 | 代入 | {2, 8, 14, 24, 29, 33} | 8 | 2 | 2 | 1 |
| 13 | 5 | 条件判定（真） | {2, 8, 14, 24, 29, 33} | 8 | 2 | 2 | 1 |
| 14 | 6 | 代入 | {2, 8, 14, 24, 29, 33} | 8 | 2 | 2 | 2 |
| 15 | 7 | 条件判定（偽） | {2, 8, 14, 24, 29, 33} | 8 | 2 | 2 | 2 |
| 16 | 9 | 条件判定（偽） | {2, 8, 14, 24, 29, 33} | 8 | 2 | 2 | 2 |
| 17 | 12 | 戻る（2） | {2, 8, 14, 24, 29, 33} | 8 | 2 | 2 | 2 |
この例題で問われること
問 search({2, 8, 14, 24, 29, 33}, 8) を呼び出したときの戻り値はどれか。
答え 2
- 戻り値になる low は、1 → 2 と変わります。
- 12行目で返す時点の値 2 が答えです。
問 6行目を1回目に実行した直後の、変数 middle の値はどれか。
答え 3
- 6行目は全部で3回実行されます。
- 実行した直後の middle は、順に 3 → 1 → 2 です。
- 1回目の直後なので、答えは 3 です。
問 6行目が実行される回数はどれか。
答え 3
- 6行目は3回実行されます。トレース表で 6行目の行を数えると確かめられます。
練習問題 標準（10問）
本試験と同じくらいの量。レベル：基礎
- 問題01 search({5, 6, 12, 13, 23, 25}, 6)
- 問題02 search({10, 15, 24, 26, 31, 35, 38, 40}, 35)
- 問題03 search({9, 10, 13, 20, 24, 25, 26, 37, 40}, 20)
- 問題04 search({1, 10, 13, 20, 26, 27, 29, 31, 40}, 13)
- 問題05 search({2, 6, 9, 12, 19, 23, 24, 25, 33}, 24)
- 問題06 search({2, 3, 17, 23, 26, 29, 36, 39}, 17)
- 問題07 search({2, 8, 13, 14, 32, 33}, 8)
- 問題08 search({16, 21, 27, 33, 37, 38}, 37)
- 問題09 search({5, 12, 24, 30, 31, 35, 39}, 35)
- 問題10 search({1, 3, 10, 15, 18, 20, 40}, 20)
もっと解く（追加の20問）
- 問題11 search({1, 15, 23, 27, 31, 33, 39, 40}, 33)
- 問題12 search({8, 10, 15, 17, 29, 30, 36}, 30)
- 問題13 search({2, 8, 16, 18, 24, 34, 36, 37}, 34)
- 問題14 search({6, 9, 21, 24, 26, 27, 31, 40}, 21)
- 問題15 search({5, 12, 28, 30, 31, 32, 33, 39}, 32)
- 問題16 search({1, 2, 3, 14, 15, 18, 25, 26}, 18)
- 問題17 search({1, 11, 13, 16, 17, 18, 20, 25, 36}, 16)
- 問題18 search({7, 8, 10, 27, 28, 35, 40}, 35)
- 問題19 search({3, 5, 10, 13, 18, 28, 33, 38}, 10)
- 問題20 search({8, 15, 19, 24, 25, 32, 38}, 19)
- 問題21 search({4, 6, 10, 14, 15, 21, 33}, 10)
- 問題22 search({5, 7, 9, 11, 13, 15, 32, 38, 39}, 32)
- 問題23 search({5, 8, 9, 12, 16, 20, 27, 30, 39}, 12)
- 問題24 search({2, 3, 9, 10, 15, 16, 18, 33, 40}, 9)
- 問題25 search({1, 5, 16, 18, 19, 25, 31, 36, 39}, 31)
- 問題26 search({4, 10, 11, 16, 32, 33, 36}, 33)
- 問題27 search({1, 2, 4, 7, 11, 13, 16, 37, 38}, 7)
- 問題28 search({3, 22, 27, 32, 35, 39}, 22)
- 問題29 search({4, 5, 8, 16, 27, 28}, 5)
- 問題30 search({1, 2, 7, 20, 26, 27, 39}, 27)