配列の中から目的の値を素早く見つけたいとき、最もよく使われる手法の一つが二分探索です。
二分探索は、ソート済み配列に対して「探索範囲を毎回半分に絞る」という非常にシンプルかつ強力なアルゴリズムです。
その計算量はO(log n)であり、線形探索のO(n)と比べると大規模データでは圧倒的に高速です。
本記事では、二分探索の時間計算量がなぜO(log n)になるのかを丁寧に解説するとともに、分割統治法との関係やソート済み配列の重要性、検索アルゴリズムとしての位置づけについても詳しく説明します。
計算量の理論から実装の基礎まで、ぜひ最後まで読んでみてください。
二分探索の計算量はO(log n)（結論）
それではまず、二分探索の計算量がO(log n)であることの結論と直感的な理由について解説していきます。
二分探索は、探索のたびに「残りの探索範囲をちょうど半分」にするアルゴリズムです。
最初にn個の要素がある配列を考えると、1回目の探索後にn/2個、2回目にn/4個、k回目にn/2^k個まで範囲が絞られます。
探索が終了するのは範囲が1個以下になったときなので、n/2^k ≦ 1、すなわちk ≧ log₂(n)が成り立ちます。
したがって、最大でもlog₂(n)回程度の比較で検索が完了し、時間計算量はO(log n)となります。
二分探索のO(log n)という計算量は非常に優れています。たとえばn=1,000,000（100万）の配列でも、最大で約20回の比較で目標値を見つけることができます。これは線形探索の最悪100万回と比べると、桁違いの効率と言えるでしょう。
この対数的な効率こそが、二分探索が大規模データの検索アルゴリズムとして広く採用されている理由です。
対数とはなにか
O(log n)を理解するには対数の概念を押さえる必要があります。
log₂(n)とは「2を何乗すればnになるか」という数値です。
log₂(1) = 0
log₂(2) = 1
log₂(4) = 2
log₂(8) = 3
log₂(1024) = 10
log₂(1,000,000) ≒ 20
nが2倍になってもlog₂(n)は1しか増えないため、O(log n)アルゴリズムは非常に緩やかにしか処理回数が増えません。
これが二分探索の強みです。
線形探索との比較
線形探索は配列の先頭から1つずつ目標値を探す方法で、時間計算量はO(n)です。
二分探索O(log n)と線形探索O(n)を比較すると、nが大きくなるほど差は顕著になります。
| 要素数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回 |
nが10億でも二分探索はわずか30回程度で完了するでしょう。
一方、線形探索は最悪10億回の比較が必要です。
二分探索の前提条件：ソート済み配列
二分探索には重要な前提条件があります。
それは、対象の配列が昇順または降順にソート済みであることです。
ソートされていない配列に二分探索を適用することはできません。
なぜなら、「中央値が目標値より大きいなら右半分は不要」という判断がソート順に依存しているからです。
したがって、未整列のデータに二分探索を使いたい場合は、まずO(n log n)のソートを行う必要があります。
二分探索のアルゴリズムと実装
続いては、二分探索の具体的なアルゴリズムの流れと実装方法を確認していきます。
二分探索のアルゴリズムは非常にシンプルで、以下の手順で進みます。
基本的なアルゴリズムの流れ
二分探索の基本的な手順は次のとおりです。
① 探索範囲の左端をleft=0、右端をright=n-1とする
② 中央のインデックスmid = (left + right) // 2 を計算する
③ a[mid] == targetなら探索成功、midを返す
④ a[mid] < targetなら左半分は不要 → left = mid + 1
⑤ a[mid] > targetなら右半分は不要 → right = mid – 1
⑥ left > rightになったら探索失敗（値なし）
⑦ ②に戻る
このシンプルな繰り返しによって、探索範囲が毎回半分になり、O(log n)の効率が実現されます。
Pythonでの実装例
以下にPythonで二分探索を実装した例を示します。
def binary_search(arr, target):
left, right = 0, len(arr) – 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid – 1
return -1 # 見つからない場合
このコードはwhile文で繰り返すたびに探索範囲が半分になるため、ループ回数はO(log n)に収まります。
Pythonにはbisectモジュールという標準ライブラリも用意されており、実用場面ではそちらを使うことも多いでしょう。
再帰版の実装と空間計算量
二分探索は再帰的にも実装できます。
def binary_search_rec(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_rec(arr, target, mid+1, right)
else:
return binary_search_rec(arr, target, left, mid-1)
再帰版の時間計算量はO(log n)と同じですが、再帰呼び出しのスタックが最大log n段積み重なるため、空間計算量はO(log n)になります。
一方、繰り返し版（iterative）の空間計算量はO(1)です。
メモリ効率を重視する場合はiterativeを選ぶとよいでしょう。
二分探索と分割統治法の関係
続いては、二分探索と分割統治法の関係について確認していきます。
分割統治法（Divide and Conquer）は、問題を小さな部分問題に分割し、それぞれを解いてから結合することで全体を解くアルゴリズム設計のパラダイムです。
分割統治法の基本概念
分割統治法の基本的なステップは「分割（Divide）」「統治（Conquer）」「結合（Combine）」の3つです。
二分探索も広い意味では分割統治法の一種と見なすことができます。
探索範囲を半分に「分割」し、目標値が含まれる半分だけを「統治（再帰探索）」し、結果をそのまま返す（結合不要）というプロセスです。
ただし、二分探索は片方の部分問題しか解かないため、一般的な分割統治よりもさらに効率的です。
分割統治法を使う他のアルゴリズム
分割統治法を使う代表的なアルゴリズムとしては、マージソート・クイックソート・高速べき乗計算・最近点対問題などがあります。
| アルゴリズム | 分割方法 | 計算量 |
|---|---|---|
| 二分探索 | 探索範囲を半分に絞る | O(log n) |
| マージソート | 配列を半分に分割してソート・マージ | O(n log n) |
| クイックソート | pivot基準に分割 | O(n log n)平均 |
| 高速べき乗 | 指数を半分に分割 | O(log n) |
これらのアルゴリズムはいずれも「問題を半分に分ける」ことでO(log n)またはO(n log n)という効率的な計算量を実現しています。
分割統治法の発想は、計算量を劇的に改善する最も重要なアルゴリズム設計原理の一つです。
二分探索の漸化式による計算量の導出
二分探索の計算量をより厳密に求めるには、漸化式を使います。
T(n) = T(n/2) + O(1)
（探索範囲を半分にする操作：O(1)、残り半分を再帰的に探索：T(n/2)）
マスター定理を適用すると：T(n) = O(log n)
このように、漸化式とマスター定理によってO(log n)が理論的に導出できます。
二分探索の応用と注意点
続いては、二分探索の応用例と実装時の注意点を確認していきます。
二分探索は単純な値の検索だけでなく、様々な場面で応用される汎用的なアルゴリズムです。
二分探索の応用例
二分探索の応用例として、まず「答えを二分探索する」という手法があります。
たとえば「ある条件を満たす最小のxを求めよ」という問題に対して、xの範囲を二分探索することで解を高速に求めることができます。
この手法は競技プログラミングで「二分探索で答えを決め打つ」と呼ばれ、非常によく使われるテクニックです。
また、データベースのインデックスもB木（B-tree）という構造を使っており、二分探索の考え方がベースになっています。
さらに、機械学習のハイパーパラメータ探索やゲームのAI（ミニマックス法）にも二分探索の発想が活かされています。
実装時の注意点（オーバーフロー問題）
二分探索を実装する際の代表的な罠が整数オーバーフローです。
mid = (left + right) / 2 という計算で、leftとrightの和が整数の最大値を超えることがあります。
【問題のある実装】
mid = (left + right) / 2 ← leftとrightが大きいとオーバーフロー
【安全な実装】
mid = left + (right – left) / 2 ← オーバーフローを防げる
Pythonでは整数の桁数に制限がないためこの問題は起きませんが、C言語やJavaでは必ず注意が必要です。
二分探索の限界と代替アルゴリズム
二分探索はソート済み配列に対してのみ有効であり、動的にデータが追加・削除される環境には向きません。
そのような場合は、挿入・削除・検索をすべてO(log n)で処理できる「平衡二分探索木（AVL木・赤黒木など）」や「B木」を使うほうが適切です。
また、ハッシュテーブルを使えば平均O(1)での検索が可能ですが、順序を保持する必要がある場合は二分探索系のデータ構造が優れています。
データの性質と操作の種類に応じて、最適なデータ構造・アルゴリズムを選ぶ判断力が重要です。
まとめ
二分探索の時間計算量はO(log n)であり、これは探索のたびに対象範囲を半分に絞ることから導かれます。
100万件のデータでもわずか20回程度の比較で目標値を見つけられる、非常に効率的な検索アルゴリズムです。
適用条件として「ソート済み配列であること」が必要ですが、この条件を満たす多くの場面で活躍します。
分割統治法の考え方をベースに持ち、競技プログラミングからデータベース設計まで幅広く応用される基礎的かつ重要なアルゴリズムです。
計算量O(log n)の意味と二分探索の仕組みをしっかり理解し、ぜひ実装と応用に役立ててください。
