C++で無限にソートされた配列から要素の位置を検索する方法

この問題では、無限に続くソート済みの数値で構成される配列が与えられます。私たちのタスクは、その無限配列の中から指定された要素の位置を見つけることです。

問題を理解するための例

入力

arr[] = {2, 4, 6, 8, 9, 12, 14, 17, …}, ele = 9

出力

4

説明

要素 9 は配列のインデックス 4 の位置に存在するため、出力は 4 となります。

解決アプローチ

ソート済みの配列から要素を効率的に検索するには、二分探索（バイナリサーチ）を使用します。しかし、この問題では配列の終端が不明であるため、通常の二分探索アルゴリズムを少し修正して使う必要があります。

具体的な手順は以下の通りです。

1. 開始ポインタ（start）を最初の位置（インデックス 0）に固定します。
2. 終了ポインタ（end）を 2 番目の位置（インデックス 1）に設定します。
3. 終了ポインタの位置にある値を確認し、その値が探したい要素（キー）より小さい場合は、終了ポインタを2 倍ずつ増加させます。同時に、開始ポインタを直前の終了ポインタの位置に更新します。
4. 終了ポインタの位置の値が探したい要素以上になった時点で、その範囲 [start, end] 内に対して通常の二分探索を実行します。

この手法により、サイズが未知の無限配列でも O(log n) の時間計算量で効率的に要素を検索できます。範囲を倍々に拡大していくため、探索範囲の特定自体も対数時間で完了します。

解決策の動作を示すプログラム

例

#include<iostream>
using namespace std;

// 通常の二分探索関数
int binarySearch(int arr[], int start, int end, int ele) {
    if (end >= start) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == ele)
            return mid;
        if (arr[mid] > ele)
            return binarySearch(arr, start, mid - 1, ele);
        return binarySearch(arr, mid + 1, end, ele);
    }
    return -1;
}

// 無限配列から要素の位置を見つける関数
int findPos(int arr[], int value) {
    int start = 0, end = 1;
    // 探索範囲を倍々に拡大
    while (arr[end] < value) {
        start = end;
        end = 2 * end;
    }
    return binarySearch(arr, start, end, value);
}

int main() {
    int arr[] = {1, 2, 4, 6, 8, 9, 12, 14, 17, 21, 45};
    int index = findPos(arr, 9);
    if (index == -1)
        cout << "Element not found!";
    else
        cout << "Element found! index = " << index;
    return 0;
}

出力

Element found! index = 5

コードの解説

findPos 関数では、まず start を 0、end を 1 に初期化します。その後、arr[end] が目的の値より小さい間、start を現在の end に更新し、end を 2 倍にしていきます。これにより、目的の値が含まれる可能性のある範囲を素早く絞り込めます。

適切な範囲が見つかったら、binarySearch 関数を呼び出して、その範囲内で再帰的に二分探索を行い、要素の正確なインデックスを取得します。要素が見つからない場合は -1 を返します。

このアルゴリズムの時間計算量は O(log n) であり、非常に大きな（事実上無限の）ソート済み配列に対しても高速に動作します。