「バイナリサーチ」という言葉はプログラミングやアルゴリズムの学習で必ず登場する重要な概念のひとつです。
線形探索との違いや具体的な仕組みがわかりにくいと感じる方も多いかもしれません。
本記事では、バイナリサーチの意味と仕組みを、二分探索の考え方・アルゴリズムの効率・具体的な計算例を交えてわかりやすく解説します。
プログラミング初学者の方からアルゴリズムの理解を深めたい方まで役立てていただける内容でしょう。
バイナリサーチを正しく理解することで、効率的なデータ検索の設計や競技プログラミングへの応用にも役立てることができます。
バイナリサーチとは「整列済みデータを半分ずつ絞り込んで目的の値を探す探索アルゴリズム」のこと
それではまず、バイナリサーチの基本的な意味と仕組みについて解説していきます。
バイナリサーチ（binary search）とは、整列（ソート）済みのデータ列に対して、探索範囲を半分ずつ絞り込むことで目的の値を効率的に見つける探索アルゴリズムです。
日本語では「二分探索」とも呼ばれ、「binary（二進法・二分）」と「search（探索）」を組み合わせた言葉です。
毎回探索範囲を半分に絞り込むため、データ量が増えても探索回数がそれほど増えないという優れた効率性を持っているでしょう。
電話帳で名前を探す際に真ん中のページから開いて前半か後半かを判断しながら絞り込む操作が、バイナリサーチの直感的なイメージとして最もわかりやすい例です。
バイナリサーチが使えるのは「整列済みのデータ」に対してのみです。ソートされていないデータに対してはバイナリサーチを適用できないため、事前のソートが必要な点を理解しておくことが重要です。
バイナリサーチの基本的な手順
バイナリサーチがどのような手順で動作するかを確認してみましょう。
【バイナリサーチの手順】
① 探索範囲の左端（low）と右端（high）を設定する
② 中央のインデックス（mid）を計算する：mid ＝ (low ＋ high) ÷ 2
③ 中央の値と目的の値を比較する
・一致した場合 → 探索成功、インデックスを返す
・目的の値が中央より小さい場合 → highをmid－1に更新（左半分に絞る）
・目的の値が中央より大きい場合 → lowをmid＋1に更新（右半分に絞る）
④ low ＞ highになるまで②〜③を繰り返す
⑤ low ＞ highになった場合 → 目的の値は存在しない
この手順を繰り返すたびに探索範囲が半分になるため、非常に高速な探索が実現できるでしょう。
バイナリサーチの具体的な計算例
整列済みの配列を使って、バイナリサーチの動作を具体的に確認してみましょう。
配列：[2, 5, 8, 12, 16, 23, 38, 45, 67, 89]（10個の要素）
目的の値：23を探す
【1回目】low＝0, high＝9, mid＝4 → 配列
＝16 < 23 → lowを5に更新
【2回目】low＝5, high＝9, mid＝7 → 配列[7]＝45 > 23 → highを6に更新
【3回目】low＝5, high＝6, mid＝5 → 配列[5]＝23 ＝ 23 → 探索成功！
10個の要素に対してわずか3回の比較で目的の値を発見
線形探索（先頭から順番に探す方法）では最大10回の比較が必要なところを、バイナリサーチでは3回で完了しているでしょう。
バイナリサーチの計算量と効率
続いては、バイナリサーチの計算量（時間複雑度）と他の探索アルゴリズムとの効率の比較を確認していきます。
計算量の理解はアルゴリズム選択の基礎となる重要な知識でしょう。
バイナリサーチの時間計算量
バイナリサーチの時間計算量はO(log n)です。
毎回探索範囲が半分になるため、n個のデータに対する最大比較回数はlog₂(n)回となります。
| データ数（n） | 線形探索（O(n)）最大比較回数 | バイナリサーチ（O(log n)）最大比較回数 |
|---|---|---|
| 10 | 10回 | 4回 |
| 100 | 100回 | 7回 |
| 1,000 | 1,000回 | 10回 |
| 1,000,000 | 1,000,000回 | 20回 |
| 1,000,000,000 | 10億回 | 30回 |
データ数が10億個であっても最大30回の比較で探索が完了するという圧倒的な効率の良さが、バイナリサーチの最大の強みでしょう。
線形探索との比較
バイナリサーチと最もシンプルな探索アルゴリズムである線形探索を比較してみます。
| 項目 | 線形探索 | バイナリサーチ |
|---|---|---|
| 時間計算量 | O(n) | O(log n) |
| 事前条件 | 不要（未整列でも可） | 整列済みデータが必要 |
| 実装の複雑さ | シンプル | やや複雑 |
| 大規模データ | 非常に遅くなる | 高速を維持 |
| 小規模データ | 十分高速 | オーバーヘッドがある場合も |
小規模なデータでは線形探索でも十分ですが、データ量が大きくなるほどバイナリサーチの優位性が際立つでしょう。
空間計算量
バイナリサーチの空間計算量（メモリ使用量）は実装方法によって異なります。
反復（ループ）で実装した場合はO(1)、再帰で実装した場合はO(log n)の空間計算量となります。
メモリ効率を重視する場合は反復による実装が推奨されるでしょう。
バイナリサーチの実装例
続いては、バイナリサーチの代表的なプログラミング言語による実装例を確認していきます。
実際のコードを通じて理解することで、バイナリサーチの動作がより具体的に把握できるでしょう。
Pythonによる反復実装
def binary_search(arr, target):
low, high = 0, len(arr) – 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid – 1
return -1 # 見つからない場合
このシンプルな実装で、O(log n)の時間計算量を持つバイナリサーチが実現できるでしょう。
バイナリサーチの注意点と典型的なバグ
バイナリサーチの実装では、いくつかの典型的なバグに注意が必要です。
最も有名なバグとして「midの計算における整数オーバーフロー」があります。
【バグの例】
mid = (low + high) // 2 → lowとhighの合計が整数の最大値を超える可能性がある
【安全な計算方法】
mid = low + (high – low) // 2 → オーバーフローを防ぐ安全な実装
特にCやJavaなどの言語では整数オーバーフローに注意が必要で、安全な計算方法を使う習慣をつけておくと良いでしょう。
バイナリサーチの応用例
バイナリサーチは単純な値の探索以外にも幅広く応用されています。
| 応用例 | 内容 |
|---|---|
| lower_bound / upper_bound | 特定の値以上・より大きい最初の要素を見つける |
| 平方根の計算 | 二分探索で数値の平方根を近似的に求める |
| 最適化問題 | 「ある条件を満たす最小・最大値」を二分探索で求める |
| データベースのインデックス | B木などのデータ構造でバイナリサーチが活用される |
競技プログラミングでは「二分探索で解ける問題」のパターンを見抜く能力が重要なスキルのひとつとなっているでしょう。
まとめ
本記事では、バイナリサーチの意味と仕組みについて、手順・計算量・線形探索との比較・実装例・応用例を交えながら解説しました。
バイナリサーチとは整列済みデータを半分ずつ絞り込んで目的の値を探すO(log n)の探索アルゴリズムで、大規模データに対して圧倒的な効率を発揮します。
整列済みデータが前提条件であること・midの計算における整数オーバーフローへの注意など、実装時のポイントを押さえておくことが重要でしょう。
lower_bound・最適化問題への応用など、バイナリサーチの概念は基本的な値探索にとどまらず幅広い問題解決に活用できます。
本記事がバイナリサーチへの理解を深め、アルゴリズム学習やプログラミングの実践に役立てば幸いです。
