C++で実装する二分探索アルゴリズム：配列内の特定の検索シーケンスを見つける方法

本プログラムでは、二分探索（バイナリサーチ）を用いて、配列の中に指定した検索シーケンス（連続する値の並び）が存在するかどうかを調べる方法を実装します。二分探索の計算量は O(log n) であり、大規模なデータセットに対しても非常に高速に動作する点が大きな特徴です。

処理の手順と擬似コード

全体の流れは以下のとおりです。

開始
　BinarySearch() 関数は、引数としてデータ配列 arr、
　要素数 n、探索範囲の start（開始）と end（終了）の
　インデックス、反復回数カウンタ、および探索対象となる
　最初の要素 b[0] を受け取る。
　反復カウンタを増やし、探索対象の値を a[mid] と比較する。
　item < a[mid] であれば前半を、そうでなければ後半を
　探索範囲として再帰的に処理を進める。
　見つかったインデックスを main() に返す。
　main() 内では、検索シーケンスの残りの要素を、
　配列上でその後に続く要素と順番に比較する。
　シーケンスが見つかったインデックス範囲を出力する。
終了

サンプルコード

以下が実際の C++ 実装例です。まず二分探索で検索シーケンスの先頭要素の位置を特定し、その位置から後続の要素が一致するかどうかを確認します。

#include<iostream>
using namespace std;
int BinarySearch(int a[], int start, int end, int item, int iter) {
    int i, mid;
    iter++;
    mid = start + (end - start + 1) / 2;
    if(item > a[end] || item < a[start] || mid == end) {
        cout<<"\nNot found";
        return -1;
    } else if(item == a[mid]) {
        return mid;
    } else if(item == a[start]) {
        return start;
    } else if(item == a[end]) {
        return end;
    } else if(item > a[mid])
        BinarySearch(a, mid, end, item, iter);
        else
            BinarySearch(a, start, mid, item, iter);
    }
int main() {
    int n, i, flag=0, Bin, len = 9, a[10]={1, 7, 15, 26, 29, 35, 38, 40, 49, 51};
    cout<<"\nEnter the number of element in the search sequence: ";
    cin>>n;
    int b[n];
    for(i = 0; i < n; i++) {
        cin>>b[i];
    }
    Bin = BinarySearch(a, 0, len, b[0], 0);
    if (Bin == -1) {
        cout<<"\nNot found.";
        return 0;
    } else {
        for(i = Bin; i < n+Bin; i++)
            if(a[i] != b[i-Bin])
                flag = 4;
                if(flag == 4)
                    cout<<"\nNot found.";
                else
                    cout<<"\nSequence found between index "<<Bin<<" and "<<Bin+n<<".";
    }
    return 0;
}

実行結果

このコードを実行すると、以下のような出力が得られます。ここでは、ソート済み配列 {1, 7, 15, 26, 29, 35, 38, 40, 49, 51} の中から「15, 26, 29, 35」という4要素のシーケンスを検索しています。

Enter the number of element in the search sequence: 4
15
26
29
35
Sequence found between index 2 and 6.

解説

このプログラムのポイントは次のとおりです。

• 二分探索による高速化： 配列は必ずソートされている必要がありますが、各ステップで探索範囲を半分に絞り込むため、線形探索の O(n) に対して O(log n) という高い効率を実現します。
• 先頭要素の特定： 検索シーケンスの最初の要素 b[0] を二分探索で探し、そのインデックスを起点とします。
• シーケンス全体の照合： 見つかったインデックス以降の要素が、検索シーケンスの残りの要素と順番に一致するかを比較します。すべて一致すれば、シーケンスが存在するインデックス範囲を出力します。

なお、この手法は「ソート済み配列内に特定の部分列が連続して含まれるか」を判定したい場合などに応用できます。境界条件（mid == end や範囲外チェック）の扱い方にも注意し、意図しない無限ループや範囲外アクセスが発生しないよう設計することが重要です。