C言語の探索アルゴリズム解説｜線形探索と二分探索の違いと実装例

探索（サーチ）とは、複数の要素で構成されるリストの中から、目的の「キー」となる要素を見つけ出す処理のことです。

• リストの中に指定した要素が存在すれば、その探索は「成功」とみなされます。

• 指定した要素がリストに存在しなければ、その探索は「失敗（不成功）」となります。

C言語で広く使われている代表的な探索手法は、主に次の2つです。

• 線形探索（Linear Search／リニアサーチ）
• 二分探索（Binary Search／バイナリサーチ）

線形探索（Linear Search）とは

線形探索は、リストの先頭から順に要素を1つずつ取り出し、キーと一致するかどうかを確認していく、最も基本的な探索手法です。アルゴリズムが単純で理解しやすく、未整列のデータにもそのまま適用できる点が大きな特徴です。

• キー要素を先頭から順に、線的に1つずつ比較していく
• 最もシンプルで実装しやすい探索手法
• リストがソートされていなくても利用できる
• 注意点 ― 要素数が多いと処理に時間がかかり、計算量はO(n)となるため、大規模データには不向き

入力（Input）

ソートされていない要素のリストと、探索したいキーの値。

出力（Output）

• 成功 ― キーがリスト内に見つかった場合
• 失敗 ― それ以外の場合

線形探索のC言語サンプルコード

以下は、線形探索を実装したC言語プログラムの例です。配列の各要素を順にキーと比較し、一致すればフラグを立ててループを抜ける仕組みになっています。

#include<stdio.h>
int main (){
    int a[50], n, i, key, flag = 0;
    printf("enter the no: of elements");
    scanf ("%d",&n);
    printf("enter the elements:\n");
    for (i=0; i<n; i++)
        scanf( "%d", &a[i]);
    printf("enter a key element:\n");
    scanf ("%d", &key);
    for (i=0; i<n; i++){
        if (a[i] == key){
            flag = 1;
            break;
        }
    }
    if (flag == 1)
        printf("search is successful:");
    else
        printf("search is unsuccessfull:");
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような結果が出力されます。

enter the no: of elements5
enter the elements:12
45
13
67
78
enter a key element:67
search is successful:

二分探索（Binary Search）とは

もう一つの代表的な手法が二分探索です。こちらは事前にソートされたリストが前提で、中央の要素とキーを比較しながら探索範囲を半分ずつ絞り込んでいくことで、目的の要素を効率的に特定します。計算量はO(log n)と非常に高速で、大量のデータを扱う場合に特に有効です。

• ソート済みのリストが必須
• 中央の要素との比較により、探索範囲を毎回半分に絞り込む
• 計算量はO(log n)で、線形探索より大幅に高速

線形探索と二分探索の比較

まとめ

C言語の探索手法には、実装が簡単で未整列データにも対応できる「線形探索」と、ソート済みデータに対して圧倒的な速度を誇る「二分探索」があります。扱うデータの規模や整列状態に応じて、最適な手法を選択することが重要です。