補間探索

1. 補間探索アルゴリズム
2. 補間探索の例
3. 補間探索アルゴリズムの実装
4. 補間探索アルゴリズムの複雑さ

補間探索は、高速で効率的な探索アルゴリズムです。これは、配列要素がソートされた配列に一様に分散しているシナリオのための二分探索アルゴリズムを改善します。これは、要求された値のプロービング位置で動作します。二分探索とは異なり、常に配列の中央に行くわけではなく、探索すべきキーの値に応じて任意の位置に行くことができる。推定位置での値を比較し、その前後の部分に探索空間を縮小していきます。例えば、辞書で単語を探索する際には、探索空間を毎回半分に分割するのではなく、その中の文字の位置に応じてページをめくるようにしています。

補間探索アルゴリズム

ここで、n の要素を含むソートされていない配列 A[] があり、与えられた要素 X を見つけたいとします。

補間探索の例

配列 (1, 3, 7, 8, 11, 15, 17, 18, 21) があり、X - 18 を求めたいとします。

補間探索アルゴリズムの実装

#include <bits/stdc++.h>
using namespace std;

int interpolation_search(int arr[], int n, int X) {
  int lo = 0;
  int hi = n - 1;
  int mid;

  while ((arr[hi] != arr[lo]) && (X >= arr[lo]) && (X <= arr[hi])) {
    mid = lo + ((X - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));

    if (arr[mid] < X)
      lo = mid + 1;
    else if (X < arr[mid])
      hi = mid - 1;
    else
      return mid;
  }

  if (X == arr[lo])
    return lo;
  else
    return -1;
}

int main(void) {
  int n = 9;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int result = interpolation_search(arr, n, x);
  if (result == -1) {
    cout << "Element not found !!";
  } else
    cout << "Element found at index " << result;
  return 0;
}

補間探索アルゴリズムの複雑さ

時間計算量

• 平均ケース

このアルゴリズムの平均ケース時間の複雑さは、O(log(logn)) のオーダーです。これは、配列内のすべての要素が一様に分布している場合に起こります。

• 最良の場合

ベストケースとは、探索しようとしている要素が補間探索で最初に探索された要素である場合です。アルゴリズムの最良の時間的複雑さは O(1) です。

• 最悪の場合

ワーストケースは対象の数値が指数関数的に増加する場合に発生します。アルゴリズムの最悪の時間的複雑度は O(n) です。

空間計算量

このアルゴリズムは一時変数以外のデータ構造を必要としないので、空間複雑度は O(1) です。