プログラム

線形探索とは

2021年3月18日

線形探索

線形探索(せんけいたんさく)とは、探索アルゴリズムの1つです。

配列やリストのような複数のデータが格納されている箱の中から、目的のデータを探し出すのが探索であり、この探索の代表的なアルゴリズムには「線形探索」「二分探索」「ハッシュ法」があります。

本記事では、探索アルゴリズムの中でも最もシンプルな手法である「線形探索」について紹介しています。

スポンサーリンク

線形探索の手順

線形探索は先頭から順に探索していく手法です。目的のデータが見つかる (配列に目的のデータがある場合)または、配列のデータをすべて確認(配列に目的のデータがない場合)したら線形探索は終了です。

今回の例では、次の配列から「2」を線形探索で探索する手順を説明していきます。

探索のアルゴリズム

【手順1】最初の要素「7」と比較

まず最初の要素である「7」を見ます。そして「7」と「2」を比較。

比較した結果、「7」は「2」ではないので次の要素「1」を見ます。

最初の要素「7」と比較

【手順2】次の要素「1」と比較

続いて次の要素である「1」と「2」を比較。

比較した結果、「1」は「2」ではないので、次の要素「3」を見ます。

次の要素「1」と比較

【手順3】次の要素「3」と比較

続いて次の要素である「3」と「2」を比較。

比較した結果、「3」は「2」ではないので、次の要素「8」を見ます。

次の要素「3」と比較

【手順4】次の要素「8」と比較

続いて次の要素である「8」と「2」を比較。

比較した結果、「8」は「2」ではないので、次の要素「2」を見ます。

次の要素「8」と比較

【手順5】次の要素「2」と比較

続いて次の要素である「2」と「2」を比較。

比較した結果、「2」を見つけることができたので探索は終了です。

次の要素「2」と比較

これで「線形探索」は終了です。
先頭から順に探索していくのでシンプルな流れで分かりやすいですね。

helpful