C++ STL 二分探索

順序付けられた範囲に値が含まれているかを調べるには、std::binary_searchを使います。戻り値は要素の有無を示す真偽値であり、一致したイテレーターや一致する値の個数は返しません。順序に関する要件を満たしていれば、vector、配列、または適切なイテレーターを持つほかの範囲にも使えます。

std::binary_search の要件を理解する

検索対象の範囲は、検索に使う比較規則に従って分割されていなければなりません。通常は、既定の比較規則と同じ順序で要素を昇順に並べておくことを意味します。その順序になっていない範囲では、結果を信頼できる有無の判定として扱えません。一度ソートした後に要素を変更したり、一部だけ並べ替えたりした場合も、前提条件を満たさなくなることがあります。

イテレーターの組は半開区間 [first, last) を表します。first は検索対象に含まれる最初の要素を指し、last は最後の要素の次を指すため、範囲には含まれません。container.begin() と container.end() を渡すと、コンテナー全体を検索します。空の範囲も有効で、その場合は一致なしを返します。要素が1つの範囲では、first がその要素を指し、last がその次を指していれば、その要素が検索対象になります。

順序規則の下で等価な要素があれば true、なければ false です。位置が必要な場合は、std::lower_bound などを使い、返されたイテレーターが last ではないことと、値が等価であることを確認してください。std::binary_searchだけでは、重複した値のうちどれに一致したかを特定できません。

ソート済み範囲で std::binary_search を使う

関数には <algorithm>、出力には <iostream>、このコンテナーには <vector> をインクルードします。次の完全なプログラムでは、存在する値と存在しない値をそれぞれ調べます。真偽値をそのまま表示するため、イテレーターを使わずに2つの結果を確認できます。

次の例を実行してください。コード内の表示ラベルと出力文字列は、バイト単位の一致を保つため英語のままです。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{2, 4, 6, 8, 10};
    const bool has_six = std::binary_search(values.begin(), values.end(), 6);
    const bool has_seven = std::binary_search(values.begin(), values.end(), 7);

    std::cout << std::boolalpha
              << "6 found: " << has_six << '\n'
              << "7 found: " << has_seven << '\n';
}

6 found: true
7 found: false

vector はすでにソートされており、各呼び出しには全体のイテレーター範囲を渡しています。例を変更するには、どちらかの検索値を変えてください。その際、vector は検索側が想定する順序のままにします。この関数が範囲をソートすることはありません。

カスタム比較関数で検索する

ユーザー定義型を使う場合は、範囲に適用する順序を定義する比較関数を渡します。検索前に、同じ比較関数でソートしてください。この例では、レコードを年齢順に並べ、同じ年齢のレコードがあれば検索対象が存在すると判定します。この比較規則では、名前は一致判定に使いません。

このセクションのコードと表示されるラベルや出力は英語のままです。

#include <algorithm>
#include <string>
#include <vector>

struct Person {
    std::string name;
    int age;
};

int main() {
    const auto by_age = [](const Person& left, const Person& right) {
        return left.age < right.age;
    };

    std::vector<Person> people{{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    std::sort(people.begin(), people.end(), by_age);

    const Person target{"", 25};
    const bool found = std::binary_search(
        people.begin(), people.end(), target, by_age);
    return found ? 0 : 1;
}

比較関数が比較するのはイテレーターではなく値です。範囲を並べる順序を定義し、範囲の要素と検索対象との比較にも適合する必要があります。この例では、名前が違っていても年齢が同じ2つのレコードは、この検索では等価です。アプリケーションでそれらを区別する必要がある場合は、区別に必要なフィールドを順序に含めるか、別の検索方法を使ってください。

二分探索でよくある間違いを避ける

• ソートされていないデータを検索する: 先に範囲をソートしてください。あるキーでソートし、別の順序で検索しても、検索要件を満たしません。
• last を要素として扱う: last は範囲に含まれません。コンテナー全体を検索するには container.end() を使い、これを逆参照しないでください。
• イテレーターが返ると思い込む: 戻り値は真偽値です。位置が必要なら std::lower_bound を使い、逆参照する前に結果を確認してください。
• ソートと異なる比較関数を使う: ソートと検索では、順序と等価性の規則を一致させる必要があります。2つのレコードを等価とみなす比較関数では、レコードの全フィールドではなく、その規則に基づいて有無が判定されます。

これらを確認すれば、関数の結果を適切に解釈できます。検索自体はライブラリが行いますが、範囲が異なる順序で準備されていることや、比較関数がデータに合っていないことまでは検出できません。