C言語で、サーチアルゴリズムの解説

C言語における代表的なサーチアルゴリズム（探索アルゴリズム）について、基本的な仕組みと実装例を解説します。探索アルゴリズムは、データの中から目的の値（キー）を見つけ出すための重要なアルゴリズムです。
​

線形探索（Linear Search）

​線形探索は、データの先頭から順番に1つずつ比較していく最もシンプルなアルゴリズムです。
​特徴: データが整列（ソート）されていなくても使用できます。
​計算量: O(N) （データ数が N のとき、最悪の場合すべての要素を確認する）
​

C言語の実装例

#include <stdio.h>

// 線形探索の関数
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // 見つかった場合はインデックスを返す
        }
    }
    return -1; // 見つからない場合
}

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 5;

    int result = linearSearch(arr, size, target);
    if (result != -1) {
        printf("値 %d はインデックス %d に見つかりました。\n", target, result);
    } else {
        printf("値が見つかりませんでした。\n");
    }
    return 0;
}

二分探索（Binary Search）

​二分探索は、あらかじめ昇順または降順にソートされたデータに対してのみ使える、非常に高速なアルゴリズムです。範囲の中央の値と探したい値を比較し、探索範囲を毎回半分に絞り込んでいきます。
​特徴: 高速ですが、事前にデータがソートされている必要があります。
​計算量: O(log N) （データが半分ずつ減るため非常に効率的）
​

C言語の実装例

#include <stdio.h>

// 二分探索の関数（配列が昇順にソートされている前提）
int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // オーバーフロー防止

        if (arr[mid] == target) {
            return mid; // 発見
        }
        if (arr[mid] < target) {
            left = mid + 1;  // 右半分を探索
        } else {
            right = mid - 1; // 左半分を探索
        }
    }
    return -1; // 見つからない場合
}

int main() {
    // 必ずソートされた配列を用意する
    int arr[] = {1, 2, 3, 5, 8, 13, 21, 34};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 13;

    int result = binarySearch(arr, size, target);
    if (result != -1) {
        printf("値 %d はインデックス %d に見つかりました。\n", target, result);
    } else {
        printf("値が見つかりませんでした。\n");
    }
    return 0;
}

アルゴリズムの比較と選び方

​データ数が少ない場合や未ソートの場合: 実装が簡単で柔軟な線形探索が適しています。
​データ数が多く、事前にソートコストをかけられる（または既にソートされている）場合: 圧倒的に高速な二分探索を選ぶべきです。