C++で均一二分探索(一様二分探索)を実装する方法とサンプルコード

均一二分探索では、あらかじめ作成しておいたルックアップテーブルを使って二分探索を実装します。シフト演算と加算を繰り返す従来の二分探索に比べ、テーブル参照のほうが高速に行えるため、二分探索の改良版と位置づけられています。この手法の時間計算量は O(log n) です。

均一二分探索の仕組み

ポイントとなるのは、配列長 n に対して「n/2, n/4, n/8, …」という差分(デルタ)を格納したテーブルです。探索は必ず配列のほぼ中央から始まり、キーが現在の要素より小さければテーブルの次の差分だけ左へ、大きければ右へ移動します。これにより、ループ内での除算やシフト計算を省き、単純な加減算とテーブル参照だけで次の比較位置を決定できます。

アルゴリズム

Begin
   データをソート済みの状態で配列に格納する
   ルックアップ配列の最大長を求め、新しい配列 del を宣言する
   データ配列の長さを n として、ルックアップ配列に n/2, n/4, … の順で 0 になるまで値を代入する
   uniBinarySearch() 関数を呼び出す
   mid に del 配列の 0 番目の値を設定し、キーと mid 番目の要素を比較する
   一致していれば、そのインデックスを main へ返す
   del の値が 0 なら要素は存在しないので、-1 を main へ返す
   キーのほうが小さければ、del に格納された次の値を減算し、del の参照位置を 1 つ進める
   キーのほうが大きければ、del に格納された次の値を加算し、del の参照位置を 1 つ進める
   関数が返したインデックスを表示し、さらに探索するかユーザーに尋ねる
End

C++ サンプルコード

#include <iostream>
using namespace std;

/* 差分(デルタ)を格納するルックアップテーブルを作成する */
void makeLookupTable(int *del, int n) {
   int power = 1, i = 0;
   do {
      int half = power;
      power *= 2;
      del[i] = (n + half) / power;  // n/2, n/4, ... を格納
      i++;
   } while (del[i - 1] != 0);
}

/* 均一二分探索の本体 */
int uniBinarySearch(int *a, int *del, int n, int key) {
   int i = del[0] - 1;   // 配列中央のインデックスから開始
   int d = 0;
   while (true) {
      if (i < 0 || i >= n)
         return -1;           // 範囲外なら未検出
      if (key == a[i])
         return i;            // 見つかった
      if (del[d] == 0)
         return -1;           // 移動できる差分が尽きた ⇒ 未検出
      if (key < a[i])
         i -= del[++d];       // 左側へ移動
      else
         i += del[++d];       // 右側へ移動
   }
}

int main(void) {
   int a[] = {2, 6, 7, 10, 12, 14, 15, 16, 20, 26};  // ソート済み配列
   int n = sizeof(a) / sizeof(a[0]);
   int del[32];

   makeLookupTable(del, n);

   char ch;
   do {
      cout << "\n探索する要素を入力してください: ";
      int key;
      cin >> key;

      int index = uniBinarySearch(a, del, n, key);
      if (index == -1)
         cout << "要素は見つかりませんでした";
      else
         cout << "要素 " << key << " は " << index + 1 << " 番目に見つかりました";

      cout << "\n\n続けて探索しますか?(y/n): ";
      cin >> ch;
   } while (ch == 'y' || ch == 'Y');

   return 0;
}

実行結果

探索する要素を入力してください: 7
要素 7 は 3 番目に見つかりました

続けて探索しますか?(y/n): y

探索する要素を入力してください: 21
要素は見つかりませんでした

続けて探索しますか?(y/n): n

コードのポイント

• ルックアップテーブル: makeLookupTable() が n/2, n/4, n/8, … という差分を生成します。たとえば n = 10 の場合は {5, 3, 1, 1, 0} となります。
• 中央から開始: 探索は del[0] - 1、つまり配列のほぼ中央のインデックスから始まります。
• 加減算のみで移動: ループ内でシフトや除算を行わず、テーブルの値を足したり引いたりするだけで次の比較位置を決められるため、処理が高速でキャッシュ効率も良好です。
• 終了条件: 差分が 0 になったら探索範囲を使い切ったことを意味し、-1 を返して「要素なし」を報告します。

なお、均一二分探索が特に有効なのは、同じ配列に対して何度も探索を繰り返すケースです。テーブル作成のコストを前もって払っておくことで、以降の各探索を高速化できます。