C++で文字列を二分探索する方法をわかりやすく解説

文字列の二分探索（バイナリサーチ）とは、ソート済みの文字列配列が与えられたとき、二分探索アルゴリズムを使って配列の中から目的の文字列を効率よく検索する手法です。

例

入力 : stringArray = {"I", "Love", "Programming", "tutorials", "point"}
検索対象 = "Programming"
出力 : 文字列はインデックス 2 で見つかりました
説明 : 文字列 "Programming" のインデックスは 2 です

入力 : stringArray = {"I", "Love", "Programming", "tutorials", "point"}
検索対象 = "coding"
出力 : -1（文字列は見つかりません）

二分探索の仕組み

二分探索は、配列の中央にある要素を基準にして探索を進める検索手法です。まず配列の中央の要素と検索対象を比較し、一致していれば探索は終了です。検索対象が中央の要素より大きければ配列の後半を、小さければ前半を探索範囲とし、範囲を半分ずつ絞り込みながら目的の要素を探します。

文字列の配列の場合も、二分探索のアルゴリズムの流れは数値の場合とまったく同じです。ただし、要素の比較には文字列比較が使われます。文字列比較では、まず先頭の文字同士を比較し、同じであれば次の文字へと進み、異なる文字が現れた時点で大小関係が確定します。

アルゴリズム

arrString : ソート済みの文字列配列
lower = 0 ; upper = n（配列の長さ）
element : 検索したい文字列

ステップ 1 : 要素が見つかるまで以下を繰り返す
ステップ 2 : mid = lower + (upper - lower) / 2
ステップ 3 : arrString[mid] == element なら、mid を返して終了
ステップ 4 : arrString[mid] < element なら、lower = mid + 1
ステップ 5 : arrString[mid] > element なら、upper = mid - 1
ステップ 6 : upper < lower になったら、-1 を返して終了（見つからない）

C++での実装例

#include<bits/stdc++.h>
using namespace std;

int binarySearchString(string arr[], string x, int n) {
    int lower = 0;
    int upper = n - 1;
    while (lower <= upper) {
        int mid = lower + (upper - lower) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] < x)
            lower = mid + 1;
        else
            upper = mid - 1;
    }
    return -1;
}

int main() {
    string arr[] = {"I", "Love", "Programming", "tutorials", "point"};
    string x = "Programming";
    int n = 5;
    int result = binarySearchString(arr, x, n);
    if (result == -1)
        cout << "要素は配列内に存在しません";
    else
        cout << "要素はインデックス " << result << " で見つかりました";
    return 0;
}

出力

要素はインデックス 2 で見つかりました

このように、二分探索を使えばソート済みの文字列配列から目的の文字列を O(log n) の計算量で効率よく検索できます。先頭から順に調べる線形探索（O(n)）と比べて、要素数が多い配列では探索回数が大幅に減るため、高速に動作する点が大きなメリットです。なお、二分探索を適用するには配列があらかじめソートされている必要がある点に注意しましょう。