二分探索 (再帰版)
二分探索 (再帰版)
このレッスンで分かること
- 探索区間を
[low, high]で表し、midの判定で左半分か右半分を呼び出します- 図のポイント (テキスト併記)
- 再帰呼び出しは毎回
区間を半分にするので、深さは最大でもlog2(n)段になります
二分探索 とは
二分探索を再帰関数で実装します。区間 [low, high] を引数で渡しながら半分ずつに分割していく方式です。
前のレッスンでは 反復版 の 二分探索 を扱いました。今回は同じアルゴリズムを 再帰 で書きます。計算量 はどちらも O(log n) で変わりませんが、コードの形が変わります。
再帰版は
分割統治 (divide and conquer)の最も基本的な例です。
基本形
探索区間を [low, high] で表し、mid の判定で 左半分 か 右半分 を呼び出します。再帰 の 終了条件 は low > high です。
Python
def binarySearchRec(arr, target):
def helper(low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return helper(mid + 1, high)
else:
return helper(low, mid - 1)
return helper(0, len(arr) - 1)JavaScript
function binarySearchRec(arr, target) {
function helper(low, high) {
if (low > high) return -1;
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) return helper(mid + 1, high);
return helper(low, mid - 1);
}
return helper(0, arr.length - 1);
}分割統治の図解
図のポイント (テキスト併記)
- 再帰呼び出しは毎回
区間を半分にするので、深さは最大でもlog2(n)段になります
再帰呼び出しは毎回 区間 を半分にするので、深さは最大でも log2(n) 段になります。n = 10^6 でも約 20 段なので、スタックオーバーフロー の心配はほぼありません。
反復版 vs 再帰版
| 観点 | 反復版 | 再帰版 |
|---|---|---|
| 計算量 | O(log n) | O(log n) |
| 空間 | O(1) | O(log n) (スタック) |
| 可読性 | ループの形 | 数学的でシンプル |
| デバッグしやすさ | デバッガで low/high を見やすい | 呼び出し履歴を追う必要あり |
| 言語サポート | どこでも書ける | 末尾再帰最適化 の有無で差が出る |
業務コードでは反復版、学習目的やアルゴリズム解説では再帰版、という使い分けが一般的です。
再帰の落とし穴
終了条件(low > high) を忘れて無限再帰mid + 1mid - 1の+1 / -1を入れ忘れ、これも無限再帰helperを外側のbinarySearchRec内に閉じこめる場合、arrを引数に渡し忘れる- 配列のコピー (
arr[low:high+1]) を渡してしまい、O(n log n)の空間計算量になってしまう (indexだけ渡すこと)
配列のスライスを毎回渡す書き方は Python JavaScript だとつい書いてしまいがちですが、O(n) のコピーが log n 回起きるので O(n log n) の 空間 を食います。index だけを渡すのが鉄則です。
サンプルケース
arr = [1, 3, 5, 7, 9, 11, 13]、target = 11 を探す場合、再帰の動きは次の通りです。
- 1 回目:
low=0, high=6, mid=3、arr[3]=7 < 11なので右半分へ - 2 回目:
low=4, high=6, mid=5、arr[5]=11で一致、return 5
log2(7) ≒ 2.8 段、つまり高々 3 段の再帰で見つかる計算と一致します。
よくある間違い
- スライスを渡す実装にしてしまい、想定以上に遅い・メモリを食う
midの更新で+1-1を忘れる- 配列が
降順ソートのときに不等号を逆にし忘れる (今回は昇順前提)
再帰でも
index 範囲 [low, high]を引数で受け取る形を覚えれば、応用がきく実装になります。
やってみよう
[1, 3, 5, 7, 9, 11] から 11 を探すと 5、[2, 4, 6] から 4 を探すと 1、空配列 [] で何かを探すと -1 を返してください。
本レッスンでは helper を内側に定義してもよいし、binarySearchRec(arr, target, low, high) のような形でも構いません。テストでは binarySearchRec(arr, target) の 2 引数で呼ばれるので、外側のシグネチャは必ず合わせてください。
よくある質問
Q. 二分探索の前提は何ですか？
A. 配列がソート済みであることです。未ソートだと結果が保証されません。実行前に Arrays.sort や sorted を呼んでから二分探索するか、最初からソート済みのデータ構造（TreeSet / SortedDict）を使ってください。
Q. 再帰版と反復版はどっちが良いですか？
A. 反復版が安定して高速です。再帰版は読みやすい代わりにスタック消費があります。配列の長さが極端に大きい（数億）場合のみ反復版を選び、教育用や読みやすさ重視なら再帰版で十分です。Python は再帰深さ制限にも注意してください。
Q. lower_bound / upper_bound とは何ですか？
A. lower_bound は target 以上が最初に現れる位置、upper_bound は target より大きい値が最初に現れる位置を返します。重複要素のある配列で「何個含まれているか」を upper - lower で求める典型イディオムで使います。
次のレッスン
次は lower_bound (最初に >= target の位置) で、二分探索を再帰関数で実装します を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 二分探索 (再帰) の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 二分探索 (再帰) とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 再帰関数で実装する
- 計算量は O(log n)
- 配列のスライスではなく index 範囲を引数で渡す
入出力例
test-cases.txt
binarySearchRec([1,3,5,7,9,11], 11) → 5
binarySearchRec([2,4,6,8], 2) → 0
binarySearchRec([1,2,3,4,5], 3) → 2
binarySearchRec([1,3,5,7], 4) → -1
binarySearchRec([42], 42) → 0