検索

検索(Search)とは、データの集合の中から特定の要素が存在するかどうか、およびその具体的な位置を特定するプロセスであり、ほぼすべてのプログラムが関わる基本的な操作です。


3つの検索アルゴリズムの比較

検索アルゴリズムの複雑度比較 — n=1000 の場合の操作回数
3つの検索アルゴリズムの比較まとめ

線形探索 O(n)

順序は不要

一つずつ比較し、シンプルで信頼性が高い

適する:データ量が小さい、または順序がない場合

二分探索 O(log n)

順序が必要

毎回半分に分割して半分を除外する

適する:順序付きデータの汎用ソリューション

補間探索 O(log log n)

順序付き + 一様分布が必要

値の比率に基づいて位置を推定

適する:一様分布の場合に最適

線形探索

最初の要素から一つずつ比較し、対象を見つけるか最後まで走査します。データの順序は不要で、時間複雑度は O(n) です。

二分探索

データはソート済みである必要があります。毎回中央の要素と比較し、検索範囲を半分に狭めます。時間複雑度は O(log n) です。

補間探索

二分探索の最適化版。中央ではなく、目標値に基づいてその可能性のある位置を推定します。データが一様分布の場合、O(log log n) を達成できます。

サンプル

#include <stdio.h>

/* 線形探索:O(n)、順序は不要 */
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

/* 二分探索:O(log n)、配列がソート済み(昇順)である必要があります */
int binarySearch(int arr[], int left, int right, int target) {
    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;  /* 見つかりませんでした */
}

/* 補間探索:平均 O(log log n)、データが一様分布である必要があります */
int interpolationSearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        /* 補間公式:値の大きさの比率に基づいて位置を推定 */
        int pos = low + ((target - arr[low]) * (high - low))
                        / (arr[high] - arr[low]);
        if (arr[pos] == target) return pos;
        if (arr[pos] < target)
            low = pos + 1;
        else
            high = pos - 1;
    }
    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    int n = 9;

    printf("線形探索 50: インデックス %d\n", linearSearch(arr, n, 50));      /* 出力: 4 */
    printf("二分探索 50: インデックス %d\n", binarySearch(arr, 0, n-1, 50)); /* 出力: 4 */
    printf("補間探索 50: インデックス %d\n", interpolationSearch(arr, n, 50)); /* 出力: 4 */
    return 0;
}

複雑度の比較まとめ

アルゴリズム時間複雑度順序が必要適用シーン
線形探索O(n)否データ量が小さい、または順序なし
二分探索O(log n)であるソート済み配列、汎用的で高効率
補間探索O(log log n)平均であるデータが一様分布する特定のシーン
その他の拡張