アルゴリズムの世界において、データの検索は最も基本的かつ重要な処理の一つです。

その中でも「二分探索（バイナリサーチ）」は、非常に高速な検索アルゴリズムとして知られており、C++を用いたシステム開発や競技プログラミングにおいて欠かすことのできない技術です。

線形探索がデータの端から順番に確認を行うのに対し、二分探索は探索範囲を半分ずつ絞り込んでいくことで、膨大なデータセットから目的の値を瞬時に見つけ出します。

C++には、この二分探索を効率的に行うための標準ライブラリが豊富に用意されています。

本記事では、二分探索の基本的な仕組みから、C++の標準ライブラリである std::binary_search、std::lower_bound、std::upper_bound の使い方、さらには独自の実装方法や「答えを二分探索する」といった応用的なテクニックまで、プロフェッショナルの視点で詳しく解説します。

目次 [ close ]
  1. 二分探索の基本概念とアルゴリズムの仕組み
  2. C++標準ライブラリにおける二分探索の活用
    1. std::binary_search関数の使い方
    2. std::lower_boundとstd::upper_boundの使い分け
    3. std::equal_rangeで範囲を効率的に取得する
  3. C++20以降のモダンな二分探索（std::ranges）
  4. 手動で二分探索を実装する方法と注意点
    1. 反復処理による実装
    2. 再帰処理による実装
  5. 応用例：答えを二分探索する（Binary Search on Answer）
  6. パフォーマンスと使用上の注意点
  7. まとめ

二分探索の基本概念とアルゴリズムの仕組み

二分探索を理解する上で最も重要な前提条件は、検索対象となるデータがソート（昇順または降順に整列）されていることです。

ソートされていないデータに対して二分探索を適用することはできません。

二分探索のアルゴリズムは以下の手順で進められます。

  1. 探索範囲の中央にある要素を確認する。
  2. 中央の値が目的の値よりも大きければ、探索範囲を「左半分（小さい方のグループ）」に絞り込む。
  3. 中央の値が目的の値よりも小さければ、探索範囲を「右半分（大きい方のグループ）」に絞り込む。
  4. 目的の値が見つかるか、探索範囲がなくなるまで 1〜3 を繰り返す。

このアルゴリズムの最大の特徴は、計算量です。

線形探索の計算量が O(N) であるのに対し、二分探索の計算量は O(log N) となります。

例えば、要素数が 100万個ある場合、線形探索では最悪 100万回の比較が必要ですが、二分探索であればわずか 20回程度の比較で済みます。

この圧倒的な効率性が、大規模データ処理において二分探索が重用される理由です。

C++標準ライブラリにおける二分探索の活用

C++の標準ライブラリ（STL）には、<algorithm> ヘッダに二分探索に関連する便利な関数が定義されています。

これらを利用することで、バグを抑えつつ高速な検索処理を実装できます。

std::binary_search関数の使い方

std::binary_search は、指定した値がコンテナ内に存在するかどうかを bool値 で返す最もシンプルな関数です。

C++
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // ソート済みのベクトルを用意
    std::vector<int> v = {1, 3, 5, 7, 9, 11, 13, 15};

    int target = 7;

    // 二分探索の実行
    if (std::binary_search(v.begin(), v.end(), target)) {
        std::cout << "値 " << target << " は見つかりました。" << std::endl;
    } else {
        std::cout << "値 " << target << " は見つかりませんでした。" << std::endl;
    }

    return 0;
}
実行結果
値 7 は見つかりました。

この関数は「あるか、ないか」を知るだけで十分な場合に適しています。

しかし、その値が「どこにあるか」というインデックス情報や、重複する値がある場合の範囲を知りたい場合には、次に紹介する関数を使用します。

std::lower_boundとstd::upper_boundの使い分け

実務で最も頻繁に利用されるのが std::lower_bound と std::upper_bound です。

これらはイテレータを返すため、要素の位置を特定するのに役立ちます。

関数名役割
std::lower_bound指定した値 以上の最初の要素 を指すイテレータを返す
std::upper_bound指定した値より 大きい最初の要素 を指すイテレータを返す

以下のサンプルコードでは、重複する値が含まれる配列に対してこれらの関数を適用しています。

C++
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 重複を含むソート済みデータ
    std::vector<int> v = {1, 2, 4, 4, 4, 6, 7, 9};

    // 4 以上の最初の要素を探す
    auto lb = std::lower_bound(v.begin(), v.end(), 4);
    // 4 より大きい最初の要素を探す
    auto ub = std::upper_bound(v.begin(), v.end(), 4);

    std::cout << "lower_bound (index): " << std::distance(v.begin(), lb) << std::endl;
    std::cout << "upper_bound (index): " << std::distance(v.begin(), ub) << std::endl;
    std::cout << "4 の個数: " << std::distance(lb, ub) << std::endl;

    return 0;
}
実行結果
lower_bound (index): 2
upper_bound (index): 5
4 の個数: 3

std::lower_bound は、値の挿入位置を探す際にも非常に便利です。

ソートされた状態を維持したまま新しい要素を追加したい場合、この関数が返す位置に挿入すれば順序を崩さずに済みます。

std::equal_rangeで範囲を効率的に取得する

std::lower_bound と std::upper_bound の両方の結果を一度に取得したい場合は、std::equal_range を使用します。

この関数は、std::pair を返し、first に lower_bound、second に upper_bound の結果を格納します。

C++
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {10, 20, 30, 30, 30, 40, 50};

    // 30 と等しい範囲を取得
    auto range = std::equal_range(v.begin(), v.end(), 30);

    std::cout << "30 の範囲: インデックス " 
              << std::distance(v.begin(), range.first) << " から " 
              << std::distance(v.begin(), range.second) - 1 << " まで" << std::endl;

    return 0;
}
実行結果
30 の範囲: インデックス 2 から 4 まで

C++20以降のモダンな二分探索（std::ranges）

C++20からは std::ranges が導入され、イテレータのペア（v.begin(), v.end()）を渡す代わりに、コンテナそのものを渡すことができるようになりました。

これにより、コードの可読性が大幅に向上し、記述ミスを防ぐことができます。

C++
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {2, 4, 6, 8, 10};

    // std::ranges::binary_search を使用（コンテナを直接渡せる）
    bool found = std::ranges::binary_search(v, 6);

    if (found) {
        std::cout << "見つかりました" << std::endl;
    }

    // lower_bound も同様に記述可能
    auto it = std::ranges::lower_bound(v, 7);
    if (it != v.end()) {
        std::cout << "7 以上の最初の値: " << *it << std::endl;
    }

    return 0;
}
実行結果
見つかりました
7 以上の最初の値: 8

std::ranges 版の関数は、プロジェクション（要素のどのメンバを比較対象にするかの指定）をサポートしているため、構造体のベクトルなどに対しても非常に柔軟に動作します。

手動で二分探索を実装する方法と注意点

標準ライブラリは強力ですが、アルゴリズムの理解を深めるため、また特殊な条件下での探索を行うために、二分探索を自前で実装できることは重要です。

反復処理による実装

最も一般的で推奨される実装方法は、while ループを用いた反復処理です。

C++
#include <iostream>
#include <vector>

// 二分探索の自前実装（反復版）
int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = static_cast<int>(arr.size()) - 1;

    while (left <= right) {
        // オーバーフローを防止する中間地点の計算
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // 見つかったインデックスを返す
        } else if (arr[mid] < target) {
            left = mid + 1; // 右側を探索
        } else {
            right = mid - 1; // 左側を探索
        }
    }

    return -1; // 見つからなかった場合
}

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50, 60};
    int target = 40;
    int result = binarySearch(v, target);

    if (result != -1) {
        std::cout << "値 " << target << " はインデックス " << result << " にあります。" << std::endl;
    } else {
        std::cout << "見つかりませんでした。" << std::endl;
    }

    return 0;
}
実行結果
値 40 はインデックス 3 にあります。

ここで重要なポイントは、中間値の計算式です。

単純に (left + right) / 2 と書くと、left と right が非常に大きな値の場合に 整数オーバーフロー が発生するリスクがあります。

そのため、left + (right - left) / 2 という書き方が安全なプラクティスとされています。

再帰処理による実装

アルゴリズムの構造を論理的に表現しやすいのが再帰を用いた実装です。

C++
#include <iostream>
#include <vector>

// 二分探索（再帰版）
int recursiveBinarySearch(const std::vector<int>& arr, int left, int right, int target) {
    if (left > right) {
        return -1;
    }

    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return recursiveBinarySearch(arr, mid + 1, right, target);
    } else {
        return recursiveBinarySearch(arr, left, mid - 1, target);
    }
}

int main() {
    std::vector<int> v = {5, 12, 23, 34, 45, 56, 67};
    int target = 23;
    int result = recursiveBinarySearch(v, 0, v.size() - 1, target);

    if (result != -1) {
        std::cout << "値 " << target << " はインデックス " << result << " にあります。" << std::endl;
    }

    return 0;
}
実行結果
値 23 はインデックス 2 にあります。

再帰版はコードが簡潔になりますが、再帰の深さによってはスタックオーバーフローのリスクがあるため、C++の実務では通常、反復版やSTL関数が好まれます。

応用例：答えを二分探索する（Binary Search on Answer）

二分探索は、単に配列から値を探すためだけの手法ではありません。

競技プログラミングなどで頻出する高度なテクニックに「答えを二分探索する」というものがあります。

これは、「条件を満たす最小（または最大）の値を求めよ」という問題において、その答えそのものを二分探索の対象にする手法です。

以下の条件を満たす場合に適用可能です。

  1. 答えの範囲（最小値と最大値）がわかっている。
  2. ある値 $x$ について「条件を満たすか？」という判定が $O(N)$ などの現実的な時間で可能である。
  3. 条件の判定結果が、ある境界を境に「偽(false)」から「真(true)」へ（あるいはその逆に）単調に変化する。

例えば、「$N$ 個の荷物を $K$ 台のトラックで運びたい。1台あたりの最大積載量を最小いくらにすれば全ての荷物を運べるか？」という問題がこれに該当します。

この積載量を二分探索で決定し、その積載量で実際に運べるかをシミュレートすることで、最適な解を高速に導き出すことができます。

パフォーマンスと使用上の注意点

二分探索を使用する際には、以下の点に注意してください。

1. データは必ずソートされていること

未ソートのデータに二分探索を適用すると、誤った結果を返します。

ソートに O(N log N) かかるため、一度しか検索を行わないのであれば線形探索（O(N)）の方が速い場合があります。

複数回の検索を行う場合に、二分探索のメリットが最大化されます。

2. イテレータの型

std::lower_bound などは、ランダムアクセスイテレータ（std::vector や std::array など）に対しては O(log N) で動作しますが、双方向イテレータ（std::list など）に対しては比較回数は O(log N) ですが、移動回数が O(N) となり、結果的に効率が悪くなります。

3. 浮動小数点数の二分探索

整数の二分探索とは異なり、double 型などの浮動小数点数で二分探索を行う場合は、誤差を考慮する必要があります。

ループの回数を固定（例：100回繰り返す）するか、while (right - left > 1e-9) のように許容誤差を指定するのが一般的です。

まとめ

二分探索は、C++において非常に強力かつ汎用性の高いアルゴリズムです。

標準ライブラリの std::binary_search や std::lower_bound を使いこなすことで、自前で複雑なロジックを組むことなく、安全かつ高速な検索処理を実装することが可能になります。

また、単なる検索に留まらず、最適化問題における「答えの二分探索」という考え方を習得することで、解決できる問題の幅が大きく広がります。

C++20の std::ranges も積極的に取り入れ、よりモダンで読みやすいコードを目指しましょう。

データ構造の特性を理解し、適切なタイミングで二分探索を選択できる能力は、エンジニアとしてのパフォーマンスを大きく左右します。

本記事で紹介した内容を参考に、日々のコーディングやアルゴリズム設計に役立ててください。