| 第２種情報処理技術者試験 |
1999年度 ＝ 平成11年度・春期 |
午前 |
問26 |
次の探索方法のうちで番兵が有効なものはどれか。
| ア ２分探索
| イ 線形探索
| ウ ハッシュ探索
| エ 幅優先探索
|
イ
番兵は、繰返しの終了の判断を簡略化させるための《目印》です。
線形探索（linear search）は、ある特定のキー値をもつ要素を、配列や表の先頭要素から順に探索するアルゴリズムです。
ここでは、以下の配列を例に解説します。
┌─┬─┬─┬─┬─┬─┐
│５│４│１│３│６│２│
└─┴─┴─┴─┴─┴─┘
この探索における繰返しの判定は、
- 目的とする値と等しい値に出会う。
- 配列や表の末尾に到達した。
のいずれかが成立することです。
ここで、目的とする値を配列の末尾に加えてみましょう。たとえば7を探索する場合は、配列の末尾に7を加えます。
┌─┬─┬─┬─┬─┬─┬─┐
│５│４│１│３│６│２│７│
└─┴─┴─┴─┴─┴─┴─┘
そうすると、探索の対象に目的とする値が存在することが保証されますので、
この探索における繰返しの判定は、
が成立することに変更できます。すなわち、判定条件が半分になり、高速化が図れます。
