検索
検索(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)、順序は不要 */
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)平均 | である | データが一様分布する特定のシーン |