C++で重複要素を含むソート済み配列から不動点を効率的に検索する方法

本記事では、与えられた配列の中から「不動点（Fixed Point）」を見つける方法を解説します。不動点とは、配列の要素の値がそのインデックスと一致している箇所のことです。例えば、arr[2] = 2 のような場合、インデックス2が不動点となります。

このプログラムは、不動点が存在すればその値を返し、存在しない場合は -1 を返します。なお、配列には負の数も含めることができ、要素は昇順にソートされているものとします。さらに、この問題では重複した要素が存在することを許容している点がポイントです。

アルゴリズムの考え方：修正版二分探索

この問題は、二分探索を使えば O(log n) の時間計算量で解くことができます。しかし、通常の二分探索をそのまま使うと、重複要素がある場合に正しい結果が得られないことがあります。そこで、探索範囲の絞り込み方に工夫が必要です。

• 左側を探索する場合： min(mid - 1, midValue) から探索を開始する
• 右側を探索する場合： max(mid + 1, midValue) から探索を開始する

この調整により、値がインデックスより大きい場合や小さい場合でも、不動点の候補となる範囲を逃さずカバーできます。

C++での実装例

#include<iostream>
using namespace std;

int getFixedPoint(int arr[], int left, int right) {
   if (right < left)
      return -1;
   int mid = (left + right) / 2;
   int midValue = arr[mid];
   // 値とインデックスが一致していれば不動点
   if (mid == arr[mid])
      return mid;
   // 左側の探索範囲を決定
   int leftindex = min(mid - 1, midValue);
   int l = getFixedPoint(arr, left, leftindex);
   if (l >= 0)
      return l;
   // 右側の探索範囲を決定
   int rightindex = max(mid + 1, midValue);
   int r = getFixedPoint(arr, rightindex, right);
   return r;
}

int main() {
   int arr[] = {-10, -5, 2, 2, 2, 3, 4, 7, 10, 12, 17};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"Fixed Point: "<< getFixedPoint(arr, 0, n-1);
}

実行結果

Fixed Point: 2

コードの解説

このサンプル配列 {-10, -5, 2, 2, 2, 3, 4, 7, 10, 12, 17} では、インデックス2の値が2であるため、不動点として 2 が出力されます。

関数 getFixedPoint() は再帰的に動作し、まず中央の要素が不動点かどうかを確認します。一致していなければ、中央の値を考慮して左右それぞれの探索範囲を決定し、再帰的に探索を続けます。重複要素があるため、単純に半分ずつに分割すると不動点を見逃す可能性がありますが、min/max による範囲調整によってこれを防いでいます。

最悪の場合の時間計算量は O(log n) であり、線形探索（O(n)）よりも高速に不動点を発見できるのがこの手法の大きな利点です。