C言語基礎｜線形探索（逐次探索）

C言語基礎｜線形探索（逐次探索）

配列って便利なんだけど、「この値、配列のどこにある？」って探したくなる場面がめちゃくちゃ多いです。
たとえば、購入履歴の中から商品IDを探す、ログの中から特定コードを探す、点数一覧から合格点を探す…みたいな感じですね。

そこで登場するのが 線形探索（逐次探索）。
これは 配列の先頭から順番に1個ずつ見ていき、目的の値と一致するかを確かめる、いちばん素直で分かりやすい探索方法です。

サンプルプログラム

ここでは「商品コードの一覧から指定コードを探す」例にします。

• 配列：codes（商品コード一覧）
• 探す値：target（探したい商品コード）
• 見つかったら：その添字を返す
• 見つからなかったら：NOT_FOUND を返す

サンプル：線形探索で商品コードを探す

プロジェクト名：chap6-16-1　ソースファイル名：chap6-16-1.c

Visual Studio でこのプログラムを実行するには、SDLチェック設定を変更しておく必要があります。
１．プロジェクト名を右クリックして、「プロパティ」をクリックします。
２．「C/C++」→「全般」→「SDLチェック」を「いいえ」に切り替えて「OK」をクリックします。

// 線形探索（逐次探索）：商品コードを探す

#include <stdio.h>

#define SIZE 6
#define NOT_FOUND -1

//--- 要素数nの配列vからtargetを探し、見つけた添字を返す ---//
int linear_search(const int v[], int n, int target)
{
    for (int i = 0; i < n; i++) {
        if (v[i] == target)
            return i;   // 見つかった場所（添字）
    }
    return NOT_FOUND;   // 見つからなかった
}

int main(void)
{
    int codes[SIZE];
    int target;

    puts("商品コードを入力してください。");
    for (int i = 0; i < SIZE; i++) {
        printf("codes[%d]：", i);
        scanf("%d", &codes[i]);
    }

    printf("探したい商品コード：");
    scanf("%d", &target);

    int idx = linear_search(codes, SIZE, target);

    if (idx == NOT_FOUND)
        puts("見つかりませんでした。");
    else
        printf("見つかりました：%d は codes[%d] にあります。\n", target, idx);

    return 0;
}

実行例

商品コードを入力してください。
codes[0]：120
codes[1]：305
codes[2]：777
codes[3]：305
codes[4]：980
codes[5]：15
探したい商品コード：777
見つかりました：777 は codes[2] にあります。

※同じ値が複数ある場合、この実装は 最初に見つかった位置 を返します。

線形探索の流れ（図でイメージ）

線形探索は、左から右へ順番にチェックしていきます。

成功と失敗の「返り値」をどう設計する？

探索は必ず 成功 or 失敗 に分かれます。
だから返り値の設計が重要です。

返り値の設計

• 添字は 0, 1, 2…と 0以上 なので
• 失敗は -1 のような「絶対に添字にならない値」にすると分かりやすいです。

計算量の話：線形探索はどれくらい時間がかかる？

線形探索は、最悪の場合 全部見る必要があります。

比較回数の目安（要素数 n）

この性質から、線形探索は O(n) と表現されます（nに比例して時間が増える）。

登場する命令・構文の書式と役割

for 文

• 書式：for (初期化; 条件; 更新) 文
• 役割：配列を先頭から順番にチェックする「走査」に最適

if 文

• 書式：if (条件) 文
• 役割：一致したかどうかを判定する

return 文

• 書式：return 式; または return;
• 役割：関数を終了し、呼び出し元へ値（返却値）を返す
  探索では「見つかった瞬間に return」で早く終わらせるのが定番です。

const

• 書式：const int v[]
• 役割：探索は配列を変更しないので、読み取り専用を明示して安全にする

表や図の補足

• 配列と添字の図は、「どの順番で探しているか」「見つかったらどの数字を返すか」を一発で理解するためのものです。
• 返り値の表は、「成功と失敗をどう区別するか」を固定化して、呼び出し側の if 判定が読みやすくなるようにしています。
• 比較回数の表は、「線形探索はシンプルだけど、要素数が増えると遅くなる」ことを感覚として持つためのものです。