C++における二分探索とは、ソート済みの配列や、一定の条件に従って順序づけられた範囲から、目的の値や条件を満たす境界を高速に探すアルゴリズムです。
探索対象の中央を確認し、その結果に応じて探索範囲を半分に狭めていきます。
この処理を繰り返すことで、すべての要素を先頭から順番に確認しなくても、効率よく目的の値を見つけられます。
二分探索は、C++の学習だけでなく、競技プログラミング、業務システム、検索処理、最適化問題などでもよく使われる重要なアルゴリズムです。
二分探索の基本的な考え方
探索範囲を半分ずつ狭める
二分探索では、まず探索対象の中央にある値を確認します。
目的の値が中央の値と一致すれば、そこで探索は終了です。
目的の値が中央の値より小さければ、中央より右側の範囲を調べる必要はありません。
反対に、目的の値が中央の値より大きければ、中央より左側の範囲を調べる必要はありません。
このように、1回の比較ごとに探索範囲を半分に減らしていくのが、二分探索の基本です。
順序があるから範囲を絞れる
二分探索が成り立つのは、探索対象に順序があるためです。
昇順に並んでいるデータであれば、中央の値と目的の値を比較することで、目的の値が左側にあるのか、右側にあるのかを判断できます。
たとえば、中央の値より目的の値が小さい場合、昇順配列では中央より右側に目的の値は存在しません。
そのため、右側をまとめて探索対象から外せます。
この「まとめて候補を捨てられる」点が、二分探索の大きな特徴です。
二分探索を使うための条件
データがソートされている必要がある
配列や vector の中から値を探す場合、二分探索を使うにはデータがソートされている必要があります。
昇順で探すなら昇順に、降順で探すなら降順に並んでいなければなりません。
ソートされていないデータでは、中央の値を見ても、目的の値が左右どちらにあるか判断できません。
そのため、二分探索を使っても正しい結果は得られません。
比較条件と並び順を一致させる必要がある
C++では、昇順だけでなく降順のデータに対しても二分探索を使えます。
ただし、降順のデータを探索する場合は、探索時の比較条件も降順に合わせる必要があります。
データの並び順と比較条件が一致していないと、二分探索は正しく機能しません。
これは、標準ライブラリの二分探索系関数を使う場合にも重要です。
データをどのルールで並べたのかと、探索時に使う比較ルールをそろえる必要があります。
条件に単調性がある必要がある
二分探索は、配列の値を探す場合だけでなく、「条件を満たす最小値」や「条件を満たす最大値」を探す場合にも使えます。
この場合に重要なのが、条件の結果に単調性があることです。
単調性とは、ある境界を境にして、条件の結果が一方向に変化する性質です。
たとえば、ある範囲で「条件を満たさない、満たさない、満たす、満たす、満たす」のように並ぶ場合、二分探索で最初に条件を満たす位置を探せます。
反対に、「満たす、満たす、満たさない、満たさない」のように変化する場合も、境界を探すことができます。
一方で、条件の結果が不規則に変化する場合は、二分探索を使えません。
二分探索の計算量
基本的な時間計算量はO(log n)
二分探索の時間計算量は、基本的に O(log n) です。
これは、探索対象の数が増えても、必要な比較回数が非常にゆるやかにしか増えないことを意味します。
たとえば、要素数が1,000個の場合、二分探索ではおおよそ10回程度の比較で目的の値にたどり着けます。
要素数が1,000,000個になっても、おおよそ20回程度の比較で済みます。
すべての要素を順番に調べる線形探索では、最悪の場合、要素数に比例した回数の確認が必要です。
それに対して、二分探索は大規模なデータでも効率よく探索できます。
空間計算量は小さい
一般的な二分探索では、探索範囲の左端、右端、中央位置など、少数の変数だけを使います。
そのため、追加で必要なメモリは基本的に少なく、空間計算量は O(1) と考えられます。
再帰で実装する方法もありますが、C++ではループで書くことが多く、その場合は余分なスタック領域もほとんど使いません。
C++で二分探索と相性がよいデータ構造
配列やvectorと相性がよい
C++で二分探索を使う場合、特に相性がよいのは配列や vector です。
これらは、任意の位置に高速にアクセスできます。
二分探索では中央の要素に何度もアクセスするため、インデックスによって素早く要素を取得できるデータ構造が向いています。
配列や vector を使えば、二分探索の効率である O(log n) を活かしやすくなります。
listとは相性がよくない
list のような連結リスト型のデータ構造では、中央の位置にすぐアクセスできません。
先頭から順番にたどる必要があるため、中央を求めるだけでも時間がかかります。
そのため、二分探索の考え方自体は適用できても、配列や vector ほど効率的にはなりません。
C++で二分探索を活用するなら、基本的には配列、vector、array など、ランダムアクセスしやすいデータ構造を使うのが適しています。
C++標準ライブラリで使える二分探索
binary_search
binary_search は、ソート済みの範囲の中に、指定した値が存在するかどうかを調べるための関数です。
戻り値は真偽値です。
つまり、値が存在するかどうかは分かりますが、その値が何番目にあるのかまでは分かりません。
そのため、位置を取得する必要がなく、単純に「その値が含まれているか」を確認したい場合に向いています。
lower_bound
lower_bound は、指定した値以上となる最初の位置を探すための関数です。
指定した値が存在する場合は、その値が最初に現れる位置を示します。
指定した値が存在しない場合は、その値を挿入しても順序が崩れない位置を示します。
この性質により、lower_bound は単なる値の探索だけでなく、挿入位置の判定や境界探索にも使えます。
upper_bound
upper_bound は、指定した値より大きい最初の位置を探すための関数です。
lower_bound が「指定値以上」の位置を返すのに対し、upper_bound は「指定値より大きい」位置を返します。
この違いは、同じ値が複数含まれているデータを扱うときに重要です。
equal_range
equal_range は、指定した値に一致する範囲をまとめて取得するための関数です。
内部的には、lower_bound と upper_bound の結果を組み合わせたような役割を持ちます。
重複する値の範囲を調べたい場合に便利です。
lower_boundとupper_boundの違い
lower_boundは指定値以上の最初の位置
lower_bound は、指定した値以上となる最初の位置を探します。
たとえば、同じ値が複数並んでいる場合、lower_bound はその値が最初に出現する位置を示します。
そのため、「ある値が最初に現れる場所を知りたい」「指定値以上の最小の要素を探したい」という場面で使いやすい関数です。
upper_boundは指定値より大きい最初の位置
upper_bound は、指定した値より大きい最初の位置を探します。
同じ値が複数並んでいる場合、upper_bound はその値の最後の位置ではなく、その次の位置を示します。
このため、lower_bound と upper_bound を組み合わせることで、特定の値が存在する範囲を表現できます。
重複要素の個数を求められる
同じ値が複数含まれている場合、lower_bound でその値の先頭位置を取得し、upper_bound でその値の直後の位置を取得できます。
この2つの位置の差を求めれば、その値が何個含まれているかが分かります。
重複を含むソート済みデータを扱う場合、この考え方は非常によく使われます。
二分探索でよくあるミス
ソートせずに使ってしまう
二分探索で最も多いミスのひとつが、ソートされていないデータに対して使ってしまうことです。
二分探索は、探索対象が正しい順序で並んでいることを前提にしています。
ソートされていない状態で使うと、結果が正しくなる保証はありません。
値を探す前に、そのデータが探索条件に合った順序で並んでいるかを確認することが重要です。
昇順と降順の条件を混同する
昇順のデータと降順のデータでは、探索時の比較条件が変わります。
昇順の考え方のまま降順データを探索すると、探索範囲の絞り込み方向が逆になってしまいます。
その結果、本来探すべき範囲を捨ててしまう可能性があります。
降順データで二分探索を使う場合は、比較条件も降順に合わせる必要があります。
境界条件を間違える
二分探索では、探索範囲の左端と右端の扱いが重要です。
範囲の右端を含めるのか、含めないのか。
中央の値を次の探索範囲に残すのか、除外するのか。
ループをどの条件で終了するのか。
これらの設計が曖昧だと、無限ループや1つずれた答えの原因になります。
二分探索は考え方自体はシンプルですが、実装では境界条件のミスが起こりやすいアルゴリズムです。
中央位置の計算でオーバーフローする可能性がある
二分探索では、探索範囲の中央位置を計算します。
このとき、左端と右端を単純に足してから2で割る方法では、非常に大きな値を扱う場合に整数の上限を超える可能性があります。
通常の小さな配列では問題になりにくいですが、大規模なデータや汎用的な処理を書く場合は注意が必要です。
より安全な中央位置の求め方を意識すると、堅牢な実装になります。
浮動小数点数に対する二分探索
浮動小数点数にも二分探索は使える
二分探索は整数だけに使うものではありません。
浮動小数点数に対しても使えます。
たとえば、平方根の近似値を求める場合や、ある条件を満たす実数の境界を探す場合にも、二分探索は有効です。
重要なのは、整数かどうかではなく、探索範囲を半分に分けながら条件判定できることです。
誤差を考慮する必要がある
浮動小数点数を扱う場合は、誤差に注意する必要があります。
整数の二分探索では、探索範囲が最終的に1つの値に絞られます。
しかし、実数の範囲には無数の値があるため、完全一致を目指すのではなく、十分に近い値を求める形になります。
そのため、浮動小数点数の二分探索では、一定回数だけ繰り返す方法や、探索範囲の幅が十分に小さくなった時点で終了する方法がよく使われます。
非連続な値に対する二分探索
値が連続している必要はない
二分探索では、値が連続している必要はありません。
数値が飛び飛びに並んでいても、順序が正しく保たれていれば二分探索を使えます。
重要なのは、値同士を比較できることと、探索対象がその比較条件に従って並んでいることです。
文字列にも二分探索は使える
二分探索は、数値だけでなく文字列にも使えます。
文字列が辞書順にソートされていれば、目的の文字列を二分探索で探すことができます。
つまり、二分探索は整数専用のアルゴリズムではありません。
大小関係や順序関係を定義できるデータであれば、二分探索の対象になります。
二分探索の応用
条件を満たす最小値を探す
二分探索は、配列の中から値を探すだけでなく、「条件を満たす最小値」を探す場合にも使えます。
たとえば、ある作業を完了できる最短時間を求める問題や、ある条件を達成できる最小の数を求める問題では、答えの候補範囲に対して二分探索を行えます。
このような使い方は、競技プログラミングや最適化問題でよく登場します。
条件を満たす最大値を探す
「条件を満たす最大値」を探す場合にも、二分探索は有効です。
ある値までは条件を満たすが、それを超えると条件を満たさなくなるような場合、二分探索で境界を見つけられます。
たとえば、制限時間内に処理できる最大量や、予算内で達成できる最大値などを求める場面で使えます。
挿入位置を探す
ソート済みのデータに新しい値を追加する場合、その値をどこに挿入すれば順序を保てるかを調べる必要があります。
このような場面でも、二分探索が使えます。
C++では、lower_bound を使うことで、指定した値を挿入しても順序が崩れない位置を探せます。
重複データの範囲を探す
同じ値が複数含まれるソート済みデータでは、二分探索を使ってその値の範囲を調べられます。
最初の位置と直後の位置を取得すれば、その値がどの範囲に存在するか分かります。
この考え方は、検索結果の件数を数える処理や、同じキーを持つデータをまとめて扱う処理で役立ちます。
手書き実装と標準ライブラリの使い分け
単純な探索なら標準ライブラリが便利
C++で単純に値の存在確認や位置取得をしたい場合は、標準ライブラリを使うのが便利です。
binary_search、lower_bound、upper_bound は、よく使われる二分探索の処理を簡潔に表現できます。
標準ライブラリを使えば、境界条件のミスを減らしやすく、コードも読みやすくなります。
複雑な条件探索では自作が有効
一方で、条件を満たす最小値や最大値を探すような問題では、自分で二分探索を書くことも多くなります。
このような場合は、単純に配列の中から値を探すのではなく、答えの候補範囲に対して条件判定を行いながら探索します。
自作することで、問題に応じた柔軟な探索が可能になります。
境界の意味を明確にすることが重要
二分探索を自分で実装する場合は、探索範囲の意味を明確にすることが重要です。
- 左端と右端をどこまで含めるのか。
- 条件を満たしたときにどちら側を残すのか。
- 条件を満たさなかったときにどちら側を捨てるのか。
これらを整理してから実装すると、バグを減らせます。
C++で二分探索を学ぶときのポイント
まずは昇順配列の探索を理解する
最初に理解すべきなのは、昇順にソートされた配列から目的の値を探す基本形です。
中央の値と目的の値を比較し、左側を探すのか右側を探すのかを判断する流れをしっかり理解しましょう。
この基本を押さえることで、標準ライブラリの関数や応用的な二分探索も理解しやすくなります。
次にlower_boundとupper_boundを理解する
C++では、lower_bound と upper_bound の理解が非常に重要です。
lower_bound は指定値以上の最初の位置、upper_bound は指定値より大きい最初の位置を探します。
この2つを使いこなせるようになると、存在確認、挿入位置の判定、重複要素の個数計算など、多くの処理を効率的に書けるようになります。
応用では単調性を意識する
二分探索の応用問題では、配列があるとは限りません。
答えの候補範囲があり、その範囲の中で条件が単調に変化するなら、二分探索を使える可能性があります。
「この条件は、ある境界を境に真偽が切り替わるか」を考えることが、応用問題で二分探索を見抜くポイントです。
C++での二分探索のまとめ
二分探索は高速な探索アルゴリズム
二分探索は、探索範囲を半分ずつ狭めることで、目的の値や条件を満たす境界を高速に見つけるアルゴリズムです。
基本的な時間計算量は O(log n) であり、大規模なデータに対しても効率よく探索できます。
ソート済みデータや単調性のある条件に使える
二分探索を使うには、探索対象がソートされていること、または条件に単調性があることが重要です。
ソート済み配列から値を探す場合はもちろん、条件を満たす最小値や最大値を求めるような問題にも応用できます。
C++では標準ライブラリを活用できる
C++では、binary_search、lower_bound、upper_bound、equal_range といった便利な関数が用意されています。
存在確認には binary_search、位置の取得には lower_bound、重複範囲の確認には lower_bound と upper_bound の組み合わせが有効です。
実装時は境界条件に注意する
二分探索は考え方がシンプルな一方で、実装では境界条件のミスが起こりやすいアルゴリズムです。
探索範囲の左端と右端をどのように扱うか、中央の値を次の範囲に含めるかどうか、終了条件をどうするかを明確にすることが大切です。
C++で二分探索を正しく使えるようになると、探索処理だけでなく、最適化問題や境界判定の問題にも対応しやすくなります。
以上、C++での二分探索についてでした。
最後までお読みいただき、ありがとうございました。
