ひとつひとつ調べていく探索法

リニアサーチ（線形探索法）は、最も単純なアルゴリズムのひとつで、初心者にわかりやすいアルゴリズムです。

方法は、「先頭から順番に探す値が見つかるまで探していくだけ」です。

配列を「直線的（リニア）に」探していくので「リニアサーチ」と呼ばれます。

単純でわかりやすいのですが、値をひとつひとつ調べていくのでデータが大量になると時間のかかる方法です。

 

 

アルゴリズムのイメージ

リニアサーチは、私たちが日常生活の中で何かを探すとき行う方法に似ています。

 

データを端から順番に「探す値が見つかるまで」調べていく方法です。

「最大値のアルゴリズム」もたくさんのデータの中から最も大きい値を「探し出すこと」なので、これと似たアルゴリズムですね。

 

サーチアルゴリズムの工夫

サーチのアルゴリズムでは、さらに結果の表し方に工夫があります。

結果には「目的の値があるかどうか」と「目的の値のある場合は、そのデータは配列のどこにあるか」という２つの情報が必要です。これらを「１つの変数」でまとめて扱おうという工夫なのです。

 

探す値が見つかったときは、そのデータの「配列の番号」は必ず「0以上の整数」です。決して「マイナスの値」にはなりません。これを利用して、

 

1. 探す値が見つかったときは、配列の番号（0以上の整数）を使う。
　
2. 探す値が見つからなかったときは、マイナスの値を使う。

 

というルールにします。

↓

こうすれば、１つの変数で「値があるか」「どこにあるか」の２つの情報を知ることができるのです。

 

1.結果の値が０以上の整数のときは、「探す値が見つかった」ことがわかります。
　
2.結果の値がマイナスのときは、「探す値が見つからなかった」ことがわかります。

 

 

具体的な手順

これを、具体的な手順で考えてみましょう。

 

準備

① まず、「結果を入れる変数」を用意します。ここには最初「マイナスの値（-1）」を入れておきます。

 

 

このあと探索していって、もし見つかったら、その配列の番号で上書きされるのでマイナスの値ではなくなります。しかし、もし最後まで見つからなかったら、値が上書きされることはありませんから、このまま「マイナスの値（-1）」となり、探す値がなかったことがわかるというわけです。

 

探索する

② 先頭から末尾までくり返し、値を調べます。

③ 「調べた値」と「探す値」が同じなら、探索完了です。

④ 「結果の変数」を「その配列の番号」で上書きして、くり返しを終了します。

 

 

結果

くり返しが終わったとき、「結果の変数」として答えが得られます。

⑤ 0以上の値だったら、値があったことがわかり、どこにあるかがその番号でわかります。

⑥ マイナスの値だったら、値がなかったことがわかります。

 

 

フローチャート

これを「フローチャート」で表してみましょう。

 

 

① まず、「結果を入れる変数（find）」を用意して「-1」を入れておきます。

② 先頭から末尾まで比較をくり返します。

③ 「探す値」と同じ値かどうかを比較します。

④ もし同じ値なら、「結果を入れる変数（find）」を「その配列の番号」で上書きして、くり返しを終了します。

 

くり返しが終わったとき、「結果を入れる変数（find）」を見ると「値があるか」「どこにあるか」がわかります。

 

このアルゴリズムの特徴（まとめ）

リニアサーチは、先頭から末尾まで真面目にひとつずつ探していくサーチです。

 

プログラム

フローチャートができたので、これを各プログラミング言語で記述してみましょう。ここではJavaScriptの例を見てみます。

ほとんどの言語では「くり返し（反復構造）」は「for文」、「条件判断（分岐構造）」は「if文」で行います。

「for文」のくり返しを中断させたいときは、「if文」と「break文」を使います。「if文」の中で「break文」が実行されると、「for文」のくり返しが終了します。

 

for文で、最初から最後まで
for文は「for (初期値; 条件式; 増減式)」と指定しますが、ここで使う「条件式」は「条件を満たすあいだはくり返す」という意味なので注意しましょう。
例えば、「for (i=0; i < n; i++)」と指定したときは、「iがnになるまでくり返す」という意味ではなく、「iがnより小さいあいだ（つまりn-1まで）くり返す」という意味です。
配列はうまくできていて、最初は0から始まり、個数もわかるので、「配列の最初から最後までをくり返すとき」は、「for (i=0; i<個数; i++)」とシンプルに書くことができます。

JavaScriptで探索する

 

JavaScriptでリニアサーチのプログラムを書いてみると、次のようになります。

入力してみよう！

<script>
    // 検索する配列データです
    var a = [10,3,1,4,2];
    // この値を探します
    var searchValue = 4;
    // 見つかったときの番号。初期値は、エラーの値（-1）にしておきます
    var findID = -1;

    // 配列のすべての値を調べていきます
    for (var i=0; i < a.length; i++) {
        // 配列の値と、探す値が同じなら
        if (a[i] == searchValue) {
            // その番号を保存して、くり返しを終了します
            findID = i;
            break;
        }
    }
    // 検索結果を表示します
    alert("見つかった番号="+ findID);
</script>

 

結果！

見つかった番号=3

いかがでしょうか。 書籍のほうでは、JavaScriptのほか、PHP、C、Java、Swift、Python、BASIC、Scratchの各言語でのプログラム例を掲載しています。言語ごとの違いや特徴などもわかりますので、興味のあるかたはぜひ書籍のほうも見てみてください。