指数探索

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

指数探索は、倍数検索やフィンガー検索とも呼ばれ、巨大なサイズの配列の要素を検索するために作られたアルゴリズムです。これは 2 段階のプロセスです。まず、アルゴリズムは対象となる要素が存在する範囲 (L, R) を見つけようとし、次にこの範囲内で二分探索を用いて対象の正確な位置を見つけます。

指数探索と名付けられているのは、インデックス pow(2,k) の要素がターゲットよりも大きい最初の指数 k を検索することで、範囲を保持する要素を見つけるからです。指数探索という名前ですが、このアルゴリズムの時間的複雑さは対数的です。配列のサイズが無限大の場合に非常に有用であり、二分探索よりもはるかに高速に解に収束します。

指数探索アルゴリズム

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

指数探索の例

配列 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) があり、X - 10 を求めたいとします。

指数探索アルゴリズムの実装

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

int binarySearch(int arr[], int lo, int hi, int x) {
  while (lo <= hi) {
    int m = lo + (hi - lo) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      lo = m + 1;
    else
      hi = m - 1;
  }
  return -1;
}

int exponentialSearch(int arr[], int n, int x) {
  if (arr[0] == x) return 0;
  int i = 1;
  while (i < n && arr[i] <= x) i = i * 2;

  return binarySearch(arr, i / 2, min(i, n - 1), x);
}

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

指数探索アルゴリズムの複雑さ

時間計算量

• 平均ケース

平均ケース時間の複雑さは O(logi) であり、ここで i は配列内の対象要素 X のインデックスです。また、要素が配列の先頭付近にある場合には、バイナリ検索よりも優れています。

• 最良の場合

ベストケースは、比較する要素が検索している要素であり、最初の繰り返しで返される場合に発生する。最良の場合の時間的複雑さは O(1) です。

• 最悪の場合

最悪の時間複雑度は平均ケースの時間複雑度と同じです。最悪の時間複雑度は O(logi) です。

空間計算量

このアルゴリズムは一時変数以外に余分な空間を必要としないので、空間の複雑さは O(1) です。