サーチのアルゴリズム (1) 線形探索法｜新しい擬似言語で学ぶ科目 B アルゴリズムとプログラミング入門

矢沢久雄
2023-04-04 更新

基本情報技術者試験は、 2023 年 4 月から新制度で実施されます。

この連載では、新制度で採用される新しい擬似言語（旧制度の擬似言語とは、表記方法に違いがあります）を使って、試験のシラバス（情報処理技術者試験における知識・技能の細目）に示されている代表的なアルゴリズムとデータ構造を、プログラミング入門者向けにやさしく解説します。受験対策としてだけでなく、アルゴリズムとプログラミングの基礎知識を習得するために、ぜひお読みください。

今回は、サーチアルゴリズムである線形探索法を取り上げます。

1 サーチアルゴリズムの基本
2 線形探索法のプログラムの例
3 break 文を使わずに繰り返しを中断するテクニック
4 線形探索の穴埋め問題にチャレンジする

サーチアルゴリズムの基本

サーチ（ search = 探索）アルゴリズムは、配列の中から目的の値を見つけるアルゴリズムです。

基本情報技術者試験のシラバスには、サーチアルゴリズムとして、

線形探索法
二分探索法
ハッシュ表探索法

が示されています。今回は、線形探索法を取り上げます。他のサーチアルゴリズムは、今後の記事の中で取り上げます。

線形探索法からサーチアルゴリズムの基本を知ることができます。

例として、図 1 に示した配列 a （要素番号は 0 から始まるとします）から、変数 x と同じ値を見つけるとしましょう。

線形探索法のアルゴリズムは、とてもシンプルです。配列の先頭から末尾に向かって要素を 1 つずつ順番に取り出して、変数 x と同じ値かどうかをチェックするだけです。先頭から末尾まで一直線にチェックするので、線形探索法と呼ぶのです。

図 1 では、変数 x と同じ値が a[2] に見つかります。この場合には、見つかった位置の 2 を探索の結果とします。これは、サーチアルゴリズムの基本です。そして、見つかったら、その時点で探索を終了します。これも、サーチアルゴリズムの基本です。

もしも、変数 x と同じ値が見つからなかった場合は、配列の要素番号としてあり得ない -1 という値を探索の結果とします（他の値でも構いませんが、多くの場合に -1 とします）。これも、サーチアルゴリズムの基本です。

線形探索法のプログラムの例

リスト 1 は、先ほど図 1 に示した線形探索法の例を、擬似言語のプログラムにしたものです。配列 a から変数 x と同じ値を探索します。

変数 pos には、探索の結果を格納します。変数 pos の初期値を、見つからなかったことを意味する -1 にしていることに注目してください。この後にある for 文による繰り返しで、 a[0] ～ a[4] を順番にチェックし、もしも見つかったら

(a[i] = x)

なら変数 pos の値を見つかった位置の i で上書きします。こうすれば、変数 pos の値は、見つからなければ -1 のままであり、見つかれば見つかった位置になります。

このように、探索の結果を「見つからなかった」を意味する -1 で初期化することも、サーチアルゴリズムの基本です。

プログラムは横スクロールできます

リスト 1 線形探索法のプログラムの例（その 1 ）

整数型の配列: a ← { 56, 34, 90, 78, 12 }
整数型: x, pos, i
x ← 90
pos ← -1

for ( i を 0 から 4 まで 1 ずつ増やす)
  if (a[i] = x)
    pos = i
    break
  endif
endfor
print(pos)

if 文の処理の中にある break は、繰り返し処理を中断する命令です。擬似言語の記述形式を示した資料に break 命令はありませんが、 C 言語、 Java 、 Python など多くのプログラミング言語に break 命令があり、旧制度の試験問題でも break 命令が使われたことがあったので、新制度の試験問題でも break 命令が使われるでしょう。

プログラムの最後にある print は、引数の値を画面に表示する手続だとします。 print(pos) によって、探索の結果が画面に表示されます。

break 文を使わずに繰り返しを中断するテクニック

先ほどのリスト 1 では、 break 命令を使いましたが、 break 命令を好まない出題者もいるでしょう。リスト 2 は、リスト 1 と同じ機能のプログラムを、 break 命令を使わずに記述した例です。リスト 1 では繰り返し処理に for 文を使っていましたが、リスト 2 では while 文を使っています。