【C++】サイズが不明なソート済み配列からターゲットを検索する方法

昇順にソートされた配列があるとします。この配列の中からターゲットとなる値を検索し、見つかった場合はそのインデックスを、存在しない場合は -1 を返す関数を定義する必要があります。

ここでのポイントは、配列のサイズが不明であるという点です。配列には ArrayReader インターフェースを通じてしかアクセスできず、ArrayReader.get(k) のように呼び出すことで、インデックス k の位置にある要素を取得できます。

例えば、入力が array = [-1,0,3,5,9,12]、target = 9 の場合、9 は配列内に存在し、そのインデックスは 4 なので、出力は 4 となります。

解決のアプローチ

この問題は、次の手順で解くことができます。

1. high := 1、low := 0 で初期化します。

2. reader.get(high) の値がターゲットより小さい間、以下を繰り返します（探索範囲を倍々に拡大）。

   • low := high

   • high = high * 2

3. low <= high の間、通常の二分探索を実行します。

   • mid := low + (high - low) / 2

   • x := reader.get(mid)

   • x == target ならば、mid を返します。

   • x > target ならば、high := mid - 1

   • それ以外の場合は、low := mid + 1

4. 見つからなければ -1 を返します。

アルゴリズムのポイント

配列のサイズがわからないため、まずは探索範囲の上限（high）を 1 から始めて 2 倍ずつ増やしていき、ターゲット以上の値が現れる位置を見つけます。この処理の計算量は O(log n) です。その後、確定した範囲 [low, high] 内で標準的な二分探索を行うことで、全体としても O(log n) の時間計算量で効率的に検索できます。

C++ 実装例

理解を深めるために、以下の実装例をご覧ください。

#include <bits/stdc++.h>
using namespace std;
class ArrayReader{
private:
    vector<int> v;
public:
    ArrayReader(vector<int> &v){
        this->v = v;
    }
    int get(int i){
        return v[i];
    }
};
class Solution {
public:
    int search(ArrayReader& reader, int target) {
        int high = 1;
        int low = 0;
        // 探索範囲の上限を倍々に拡大
        while (reader.get(high) < target) {
            low = high;
            high <<= 1;
        }
        // 二分探索
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int x = reader.get(mid);
            if (x == target)
                return mid;
            if (x > target) {
                high = mid - 1;
            }
            else
                low = mid + 1;
        }
        return -1;
    }
};
main(){
    Solution ob;
    vector<int> v = {-1,0,3,5,9,12};
    ArrayReader reader(v);
    cout<<(ob.search(reader, 9));
}

入力例

{-1,0,3,5,9,12}, 9

出力例

4

まとめ

サイズが不明なソート済み配列の検索では、「まず探索範囲を指数的に拡大して境界を見つけ、その後に二分探索を行う」という二段階のアプローチが有効です。これにより、配列の長さを直接知らなくても O(log n) の効率でターゲットを検索できます。