BohYoh.com《第２種情報処理技術者試験》2000年度＝平成12年度・秋期午前問58

第２種情報処理技術者試験

2000年度＝平成12年度・秋期

午前

問58

　配列A [1]からA [n]に格納されたデータの中から、番兵を用いてx を探索する適切な流れ図はどれか。

解答

　エ

解説

　問題で示されているアルゴリズムは、番兵を用いた線形探索（linear search）です。線形探索は、ある特定のキー値をもつ要素を、配列や表の先頭要素から順に探索するアルゴリズムです。
　ここでは、以下の配列を例に解説します。

　　　┌─┬─┬─┬─┬─┬─┐ 　　　│５│４│７│３│６│２│ 　　　└─┴─┴─┴─┴─┴─┘

　線形探索における繰返しの判定は、

のいずれかが成立することです。
　ここで、目的とする値を配列の末尾に加えてみましょう。たとえば7を探索する場合は、配列の末尾に7を加えます。

　　　┌─┬─┬─┬─┬─┬─┬─┐ 　　　│５│４│７│３│６│２│７│ 　　　└─┴─┴─┴─┴─┴─┴─┘

　そうすると、探索の対象に目的とする値が存在することが保証されますので、この探索における繰返しの判定は、

が成立することに変更できます。すなわち、判定条件が半分になり、高速化が図れます。
　番兵の値は探索する値xであり、それを要素A [1], A [2], A [n ]の後ろ、すなわちA [n + 1]に代入しますので、エが正解です。