C++で配列内の不動点（インデックスと等しい値）を二分探索で効率的に検索する方法

本記事では、ソート済みの配列から「不動点（Fixed Point）」と呼ばれる特殊な要素を検索する方法を解説します。不動点とは、要素の値がそのインデックス（添字）と一致している要素のことです。プログラムは不動点が存在すればその値を返し、存在しない場合は -1 を返します。なお、配列には負の数が含まれることもあり、データ要素はソート済みであると仮定します。

二分探索による効率的なアプローチ

すべての要素を順に確認する線形探索では O(n) の計算量が必要ですが、配列がソート済みであるという性質を利用すると、二分探索（バイナリサーチ）によって O(log n) という高速な計算量でこの問題を解くことができます。アルゴリズムの流れは以下の通りです。

1. まず配列の中央の要素を確認し、その値がインデックスと一致していれば、それが不動点なのでその値を返します。
2. 一致しない場合、中央のインデックスがその位置の値より大きければ、不動点は右側の領域に存在する可能性があるため、右半分に対して同じ処理を再帰的に行います。
3. 逆に、インデックスが値より小さい場合は、不動点は左側にある可能性が高いため、左半分を探索します。
4. 探索範囲がなくなった場合は不動点が存在しないと判断し、-1 を返します。

C++での実装例

以下が、二分探索を再帰的に実装したC++のコード例です。

#include<iostream>
using namespace std;

// 二分探索で不動点を探す再帰関数
int getFixedPoint(int arr[], int left, int right) {
    if(right >= left){
        int mid = (left + right)/2; // 中央のインデックスを計算
        if(mid == arr[mid]) // 値とインデックスが一致 → 不動点
            return mid;
        if(mid > arr[mid]) // インデックスが値より大きければ右側を探索
            return getFixedPoint(arr, (mid + 1), right);
        else // そうでなければ左側を探索
            return getFixedPoint(arr, left, (mid -1));
    }
    return -1; // 不動点が見つからない場合
}
int main() {
    int arr[] = {-10, -1, 0, 3, 10, 11, 9, 50, 56};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Fixed Point: "<< getFixedPoint(arr, 0, n-1);
}

実行結果

Fixed Point: 3

この例では、インデックス 3 の位置に値 3 が格納されているため、不動点として 3 が出力されます。

計算量について

このアルゴリズムの時間計算量は O(log n) です。各ステップで探索範囲が半分に絞られていくため、要素数が多い配列でも高速に動作します。空間計算量は再帰呼び出しに伴うスタックの使用により O(log n) となりますが、ループによる反復実装に書き換えれば O(1) に抑えることも可能です。