[C言語のはじめ方] Part30: 基本的な探索（線形探索・2分探索）

プログラミングでは、たくさんのデータの中から特定のデータを探し出す場面がよくあります。例えば、会員リストから特定の名前を探したり、商品データベースから特定のコードの商品を見つけたりする場合です。このような「探索」を行うための基本的なアルゴリズムとして、「線形探索」と「2分探索」があります。

このステップでは、これら2つの探索アルゴリズムの仕組みと、C言語での実装方法を学びます。それぞれの特徴を理解し、状況に応じて適切なアルゴリズムを選べるようになりましょう！

線形探索は、最もシンプルで直感的な探索アルゴリズムです。配列の先頭から要素を一つずつ順番にチェックし、目的のデータが見つかるか、配列の最後まで探し終わるまで続けます。

特徴

• シンプル: アルゴリズムの考え方が非常に簡単で、実装も容易です。
• 事前準備不要: 配列のデータがソート（整列）されている必要がありません。どんな順番のデータに対しても使えます。

欠点

• 効率が悪い場合がある: 配列の要素数が多い場合、目的のデータが末尾にある、または存在しない場合、すべての要素をチェックする必要があるため、時間がかかることがあります。

C言語での実装例

指定された整数配列の中から、特定の数値（キー）を探す線形探索の関数例です。見つかった場合はその要素のインデックス（添え字）を、見つからなかった場合は -1 を返します。

#include <stdio.h>

// 線形探索関数
// arr: 探索対象の配列
// n: 配列の要素数
// key: 探したい値
int linear_search(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        // 配列の要素を先頭から順に比較
        if (arr[i] == key) {
            return i; // 見つかったらそのインデックスを返す
        }
    }
    return -1; // 最後まで見つからなかった場合
}

int main() {
    int numbers[] = {15, 8, 22, 5, 19, 10};
    int n = sizeof(numbers) / sizeof(numbers[0]); // 配列の要素数を計算
    int search_key = 19;
    int not_found_key = 100;

    int result1 = linear_search(numbers, n, search_key);
    if (result1 != -1) {
        printf("%d は配列のインデックス %d で見つかりました。\n", search_key, result1);
    } else {
        printf("%d は配列内に見つかりませんでした。\n", search_key);
    }

    int result2 = linear_search(numbers, n, not_found_key);
    if (result2 != -1) {
        printf("%d は配列のインデックス %d で見つかりました。\n", not_found_key, result2);
    } else {
        printf("%d は配列内に見つかりませんでした。\n", not_found_key);
    }

    return 0;
}

計算量

線形探索の計算量は、最悪の場合（データが末尾にあるか存在しない場合）に配列の要素数 n に比例するため、O(n) と表現されます。平均的な場合も O(n) となります。

2分探索は、ソート済みの配列に対して非常に高速に動作する探索アルゴリズムです。配列の中央の要素と目的の値を比較し、目的の値が中央値より小さい場合は配列の前半部分、大きい場合は後半部分に探索範囲を絞り込みます。この操作を繰り返すことで、効率的に目的のデータを見つけ出します。

特徴

• 高速: 探索範囲を半分ずつ絞り込んでいくため、データ量が非常に多くても高速に探索できます。
• 効率的: 大規模なデータセットの探索に適しています。

欠点

• ソートが必要: 事前に配列がソートされている必要があります。ソートされていない場合は、まずソートを行うコストがかかります。
• 実装がやや複雑: 線形探索に比べると、範囲を管理するための変数や条件分岐が少し複雑になります。

C言語での実装例

ソート済みの整数配列の中から、特定の数値（キー）を探す2分探索の関数例です。線形探索と同様に、見つかった場合はそのインデックスを、見つからなかった場合は -1 を返します。

#include <stdio.h>

// 2分探索関数
// arr: 探索対象のソート済み配列
// n: 配列の要素数
// key: 探したい値
int binary_search(int arr[], int n, int key) {
    int left = 0;      // 探索範囲の左端のインデックス
    int right = n - 1; // 探索範囲の右端のインデックス
    int mid;           // 探索範囲の中央のインデックス

    while (left <= right) {
        mid = left + (right - left) / 2; // 中央のインデックスを計算 (オーバーフロー対策)

        if (arr[mid] == key) {
            return mid; // 見つかったらそのインデックスを返す
        } else if (arr[mid] < key) {
            // 中央の値よりキーが大きい場合、探索範囲を右半分に絞る
            left = mid + 1;
        } else {
            // 中央の値よりキーが小さい場合、探索範囲を左半分に絞る
            right = mid - 1;
        }
    }

    return -1; // 見つからなかった場合
}

int main() {
    // 注意: 配列はソート済みであること！
    int numbers[] = {5, 8, 10, 15, 19, 22};
    int n = sizeof(numbers) / sizeof(numbers[0]);
    int search_key = 19;
    int not_found_key = 100;

    int result1 = binary_search(numbers, n, search_key);
    if (result1 != -1) {
        printf("%d は配列のインデックス %d で見つかりました。\n", search_key, result1);
    } else {
        printf("%d は配列内に見つかりませんでした。\n", search_key);
    }

    int result2 = binary_search(numbers, n, not_found_key);
    if (result2 != -1) {
        printf("%d は配列のインデックス %d で見つかりました。\n", not_found_key, result2);
    } else {
        printf("%d は配列内に見つかりませんでした。\n", not_found_key);
    }

    return 0;
}

コード中の `mid = left + (right – left) / 2;` という計算方法は、`mid = (left + right) / 2;` と比べて、`left + right` が整数型の最大値を超えてしまうオーバーフローを防ぐための一般的なテクニックです。

計算量

2分探索の計算量は、1回の比較で探索範囲が半分になるため、非常に効率的です。計算量は O(log n) と表現されます。データ数が2倍になっても、探索に必要な比較回数は1回増えるだけです。

それぞれのアルゴリズムの特徴を比較してみましょう。

では、実際にどちらの探索アルゴリズムを使えば良いのでしょうか？以下の点を考慮して選びましょう。

• データはソートされていますか？
  • はい → データ数が多ければ、高速な2分探索が有利です。
  • いいえ → 線形探索を使うか、まずデータをソートしてから2分探索を使います。ソートのコストも考慮する必要があります。頻繁に探索を行う場合は、最初にソートしておく価値があるかもしれません。
• データ数はどれくらいですか？
  • 少ない → どちらを使っても速度差はほとんど問題になりません。実装が簡単な線形探索で十分な場合が多いです。
  • 多い → 2分探索の速度メリットが大きくなります（ただしソート済みの必要があります）。
• 実装の手間は？
  • 手早く実装したい、アルゴリズムが単純な方が良い場合は線形探索が適しています。

多くの場合、データが大量で、かつ頻繁に探索が行われるシステムでは、データをソートしておき、2分探索を利用するのが効率的です。

今回は、基本的な探索アルゴリズムである「線形探索」と「2分探索」について学びました。

• 線形探索: シンプルで実装が簡単。データがソートされていなくても使えるが、効率は O(n)。
• 2分探索: ソート済みのデータに対して非常に高速 (O(log n))。データ量が多い場合に効果を発揮する。

これらのアルゴリズムは、より複雑なデータ構造やアルゴリズムを学ぶ上での基礎となります。それぞれの特性を理解し、状況に応じて適切な方法を選択できるようになりましょう。

次は、スタックやキューといった、データを効率的に管理するための「データ構造」について学んでいきましょう！