二分探索

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

二分探索は、最も一般的で効率的な検索アルゴリズムです。実際、これは最速の検索アルゴリズムです。ジャンプソートと同様に、配列をソートする必要があります。これは divide and conquer アプローチに基づいており、配列を 2つに分割してから中間の項目と検索している項目を比較します。真ん中の項目が一致した場合は、真ん中の要素のインデックスを返し、そうでない場合は、項目の値に応じて左半分と右半分に移動します。

二分探索アルゴリズム

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

二分探索の例

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

二分探索アルゴリズムの実装

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

二分探索アルゴリズムの複雑さ

時間複雑度

• 平均ケース

二分探索を行う場合、半分を探索し、もう片方の半分を破棄するので、配列のサイズは毎回半分になります。

時間的複雑さの式は再帰によって与えられます。

T(n) = T(n/2) + k , k is a constant.

この再帰の結果は logn であり、時間的複雑さは O(logn) のオーダーです。これは線形探索やジャンプ探索よりも高速です。

• 最良の場合

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

• ワーストケース

ワーストケースの時間複雑度は平均ケースの時間複雑度と同じです。ワーストケースの時間複雑度は O(logn) です。

空間計算量

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

再帰的な実装の場合、再帰的な呼び出しスタックに必要な空間があるため、空間の複雑さは O(logn) です。