配列内の特定の値を検索するC++プログラム：二分探索による効率的な実装

問題概要

ソート済みのn個の整数値を含む配列「arr」が与えられているとします。さらに、サイズqの配列「query」も与えられ、「query」内の各値が配列「arr」に存在するかどうかを判定する必要があります。

• queryの値がarrに存在する場合：「Present」と、その値が位置するインデックスを出力する
• queryの値がarrに存在しない場合：「Not present」と、queryの値より大きい最小値がarr内で位置するインデックスを出力する

なお、配列は1-indexed（先頭の要素を1番目として数える）であることに注意してください。

入力例

n = 8, arr = {1, 2, 3, 4, 7, 9, 12, 15}, q = 3, query = {1, 5, 8} の場合、出力は次のようになります。

Present 1
Not present 5
Not present 6

出力の解説

• 1番目のクエリ（1）： arr の位置1に存在するため「Present 1」と出力されます。
• 2番目のクエリ（5）： arr には存在しません。5より大きい最小値は7で、その位置は5番目のため「Not present 5」と出力されます。
• 3番目のクエリ（8）： arr には存在しません。8より大きい最小値は9で、その位置は6番目のため「Not present 6」と出力されます。

解決のアプローチ

この問題は、C++標準ライブラリのlower_bound()関数を使うことで効率的に解くことができます。lower_bound()は二分探索によって、指定した値「以上」となる最初の要素の位置を O(log n) で見つけることができます。

アルゴリズムの手順

1. 配列 values を定義し、arr のすべての要素を挿入します。
2. i := 0 から開始し、i < n の間、i を1ずつ増やしながら、values の末尾に arr[i] を追加します。
3. i := 0 から開始し、i < q の間、i を1ずつ増やしながら以下を実行します。
   • idx := values 内で query[i] 以上となる最初の要素の位置（先頭からの相対位置）を求めます。
   • values[idx] が query[i] と一致する場合は「Present」を、そうでなければ「Not present」を出力します。
   • idx + 1 を出力します（1-indexed への変換）。

C++実装例

以下の実装を見て、理解を深めましょう。

#include <vector>
#include <iostream>
using namespace std;

void solve(int n, int arr[], int q, int query[]) {
    vector<int> values;
    for(int i = 0; i < n; i++){
        values.push_back(arr[i]);
    }
    for(int i = 0; i < q; i++) {
        int idx = lower_bound(values.begin(), values.end(),
        query[i]) - values.begin();
        if (values[idx] == query[i])
            cout << "Present ";
        else
            cout << "Not present ";
        cout << idx + 1 << endl;
    }
}

int main() {
    int input_arr[] = {1, 2, 3, 4, 7, 9, 12, 15};
    int query_arr[] = {1, 5, 8};
    solve(8, input_arr, 3, query_arr);
    return 0;
}

入力

int input_arr[] = {1, 2, 3, 4, 7, 9, 12, 15};
int query_arr[] = {1, 5, 8};
solve(8, input_arr, 3, query_arr);

出力

Present 1
Not present 5
Not present 6

計算量について

各クエリに対してlower_bound()による二分探索を行うため、クエリ1件あたりの処理時間は O(log n)、q件のクエリ全体では O(q log n) となります。1件あたり O(n) かかる線形探索と比べて大幅に高速であり、特にデータ数が多い場合に効果を発揮します。