プログラミング定番アルゴリズム(1)「線形探索法」

アルゴリズムの中でも、特に定番とされているものがあります。定番アルゴリズムを学ぶことは、プログラミング技術の向上に役立ちます。本日は、そんな定番アルゴリズムから1つ取り上げて紹介したいと思います。

「アルゴリズム とは」Google検索

定番アルゴリズムとは？

アルゴリズムは、大きく分けると、探索、整列、数値計算、文字列探索の４つの種類があります。そして、その種類ごとに、基本的な処理手順を持っているアルゴリズムがあり、それらが定番アルゴリズムとされています。

引用元：アルゴリズムを、はじめよう伊藤静香 P88

定番アルゴリズムの種類

定番アルゴリズムの種類は、以下の通りです。

探索

• 線形探索法（リニアサーチ））
• 二分探索法（バイナリサーチ）
• ハッシュ探索法

整列

• 単純選択法（選択ソート）
• 単純交換法（バブルソート）
• 単純挿入法（挿入ソート）
• クイックソート
• マージソート
• ヒープソート
• シェルソート

数値計算

• エラトステネスのふるい
• ユークリッドの互除法
• ガウスの消去法（掃き出し法）
• 台形公式（台形測）
• ダイクストラ法
• 二分法
• ニュートン法（ニュートン・ラフソン法）

文字列探索

• 力任せの探索法
• KMP（クヌース・モリス・プラット法）
• BM（ボイヤー・ムーア法）

線形探索法（リニアサーチ）

探索アルゴリズムとは、簡単に言うと「目的のデータを探し出すアルゴリズム」のことです。「線形探索法」は、その中でも最も基本的なアルゴリズムです。

例えば、箱の中に数字の書かれた紙が入っていて、箱を開けるまで紙に書かれた数字は分からない時、その中から「5」と書いてある紙を探したいとします。これを実際に線形探索法で探すとすると、以下のような形になると思います。

1. 箱をあけ、紙が5か確認する
2. 5でなければ次の箱をあける

これが線形探索法です。左から順番に1つずつ探す、単純なアルゴリズムです。

実際にプログラムに落とし込む

先ほどの箱は配列と考えます。

（PHPの場合）
$datas = [2, 1, 3, 5, 4];

for ($i = 0; $i < count($datas); $i++) {
    if ($datas[$i] == 5) {
        return print($i + 1 . '番目に見つかりました。');
    }
}

このように配列を使って順番に検索していくアルゴリズムを、線形探索法といいます。とてもシンプルで、処理の流れも簡単なプログラムです。しかし、データが大きくなるにつれて処理時間も長くなってしまうというデメリットもあります。

まとめ

ここまでお読みいただきありがとうございました。次回はまた、次のアルゴリズムについてご紹介できればと思います。