二分探索の原理：半分を捨て続ける
中央との1回の比較から、なぜ候補の半分を調べずに済むのか。整列という前提、O(log n) の意味、境界探索、そして「100階建てと2個の卵」の古典問題まで
二分探索とは
二分探索（binary search）は、整列済みのデータから目的の値を探すアルゴリズムです。探索中の範囲の中央を調べ、目的の値が中央より大きいか、小さいかによって、次に調べる範囲を半分に絞ります。
重要なのは、単に中央を見ることではありません。データが小さい順に並んでいるからこそ、中央より小さい値は右側に存在せず、中央より大きい値は左側に存在しないと言い切れます。この根拠によって、片側を調べずに捨てられます。
中央を選ぶ
現在の候補範囲を low から high とし、その中央 mid の値を1つ調べます。
大小を比べる
中央の値と目的の値を比較し、一致・中央より左・中央より右のどれかを判断します。
半分を捨てる
整列順を根拠に、目的の値が存在し得ない側を候補から完全に除外します。
二分探索の本質は「中央を調べること」ではなく、「1回の判定で、答えを含まない半分を証明つきで捨てること」です。
55を探す動きを追う
可視化ツールと同じ、5から100まで5刻みで並んだ20個の値から55を探してみます。low と high は、まだ答えが存在する可能性のある範囲の両端です。
55 を探す: [5, 10, 15, ..., 95, 100] 比較 探索範囲 中央値 判断 1 index 0..19 50 55 > 50 -> 左半分を捨てる 2 index 10..19 75 55 < 75 -> 右半分を捨てる 3 index 10..13 60 55 < 60 -> 右半分を捨てる 4 index 10..10 55 一致！ 20 個の候補を 4 回の比較で発見
最初の比較では50より大きいと分かるため、50以下の10個を一度に除外できます。次は75より小さいので75以上を除外し、60より小さいので60以上を除外します。残った55と一致して終了です。
各段階で守っている条件は「目的の値が配列に存在するなら、必ず low から high の範囲内にある」です。この条件をループ不変条件と呼びます。範囲を更新しても条件が壊れないことが、アルゴリズムの正しさの根拠になります。
なぜ O(log n) なのか
先頭から順に調べる線形探索では、候補がn個なら最悪n回の比較が必要です。二分探索では、1回ごとに候補が n、n/2、n/4、n/8 と半分になります。
線形探索：O(n)
100万個の値では、目的の値が末尾にあると最大100万回比較します。データが倍になれば、比較回数もほぼ倍になります。
二分探索：O(log n)
100万個の整列済みデータでも最大約20回です。データが倍になっても、必要な比較は原則1回しか増えません。
n / 2^k <= 1 となるまで絞るため、k >= log2(n)
20個なら最大5回、約100万個なら最大20回、約10億個でも最大30回ほどです。大きなデータになるほど、半分を捨てる効果が際立ちます。
計算量 O(log n) には、中央の要素へすぐアクセスできる配列などを使う前提があります。連結リストでは中央まで辿る時間がかかるため、比較回数だけが少なくても全体は同じ速さになりません。
TypeScriptで実装する
基本実装では、low と high の両方を探索範囲に含めます。範囲が残っている low <= high の間だけ中央を比較します。
function binarySearch(sorted: number[], target: number): number { let low = 0 let high = sorted.length - 1 while (low <= high) { // low + high のオーバーフローを避ける形 const mid = low + Math.floor((high - low) / 2) const value = sorted[mid] if (value === target) return mid if (value < target) low = mid + 1 else high = mid - 1 } return -1 }
中央より右へ進むときは low = mid + 1、左へ進むときは high = mid - 1 とします。mid 自身は比較済みなので候補から外します。+1 や -1 を忘れると、同じ中央を選び続けて終了しないことがあります。
この実装は一致する要素を1つ返します。同じ値が複数あるときに最初または最後の位置を求めるには、見つけても終了せず、さらに左または右の境界を探す変形が必要です。
配列の検索から「境界の探索」へ
二分探索は、値そのものを探す場合だけに使うものではありません。ある判定が途中まで false で、ある地点から先はすべて true になるなら、最初に true になる境界を二分探索できます。この性質を単調性と呼びます。
階: 1 2 3 ... 41 42 | 43 44 ... 100 割れる?: false false false ... false false | true true ... true ^ 最初に true になる境界
中央で predicate(mid) が true なら、答えは中央自身か、さらに左にあります。false なら答えは右側です。この判定でも、毎回どちらか半分を捨てられます。
function firstTrue( low: number, high: number, predicate: (value: number) => boolean ): number { let answer = high + 1 // true がなかった場合 while (low <= high) { const mid = low + Math.floor((high - low) / 2) if (predicate(mid)) { answer = mid high = mid - 1 // もっと左に最初の true があるか調べる } else { low = mid + 1 } } return answer }
商品の価格が予算を初めて超える位置、処理能力を満たす最小のサーバー台数、条件を満たす最短時間など、「最小の成功値」や「最大の失敗値」を求める問題は、この境界探索として考えられます。
有名な問題：100階建てと2個の卵
境界探索を理解したところで、古典的な面接問題を考えます。この問題は一見すると二分探索そのものですが、追加の制約がアルゴリズムの選択を変えます。
問題
100階建ての建物と、同じ強度の卵が2個あります。卵が割れずに落とせる最も高い階Fを特定してください。F以下なら割れず、Fより上なら必ず割れます。割れなかった卵は再利用できますが、割れた卵は使えません。最悪の場合の落下回数を最小にするには、どの階から試せばよいでしょうか。
「Googleの入社問題」という呼び方について
この問題は「昔のGoogleの面接・入社試験で出た問題」として広く知られ、Google面接で実際に問われたという受験者報告もあります。一方、Googleが公式な過去問題として公開したものではなく、Microsoftなど別企業の問題として紹介される場合もあります。ここでは出題元を断定せず、「Google面接問題として有名な古典問題」という通称として扱います。
階が高くなるにつれて「割れない」から「割れる」へ一度だけ変わるため、判定には単調性があります。では50階から始め、半分ずつ調べればよいのでしょうか。
卵を何個でも使えるなら二分探索
50階で試し、結果に応じて1〜49階または51〜100階へ進めます。卵を失っても続けられるなら、101通りの境界を最大7回ほどで特定できます。
卵が2個だけなら単純な二分探索ではない
50階で1個目が割れると、残る卵は1個です。25階で再び割れば探索を続けられないため、1階から49階まで順番に確認するしかありません。半分を捨てる判定そのものが資源を消費します。
最適戦略では、最初の卵を14階から落とします。割れなければ次は13階上の27階、その次は12階上の39階というように、間隔を1ずつ短くします。割れたら、直前に安全だった階の次から2個目で1階ずつ調べます。
第1の卵を落とす階: 14 -> 27 -> 39 -> 50 -> 60 -> 69 -> 77 -> 84 -> 90 -> 95 -> 99 -> 100 +13 +12 +11 +10 +9 +8 +7 +6 +5 +4 （100で打ち切り） 途中で割れたら: 直前に割れなかった階の次から、第2の卵で 1 階ずつ確認する 最悪回数を 14 にそろえる: 1 + 13 = 2 + 12 = 3 + 11 = ... = 14
14 + 13 + 12 + ... + 1 = 105 >= 100
13 + 12 + 11 + ... + 1 = 91 < 100
最大d回で調べるとします。最初の卵が1回目で割れたら残りd−1階、2回目なら残りd−2階を2個目で順番に調べられるため、扱える階数の上限は d + (d−1) + ... + 1 です。13回では91階までしか覆えず、14回なら105階を覆えます。したがって100階の最悪回数14は、達成可能であるだけでなく最小です。
この古典問題の教訓は「二分探索を使う」ことより、「二分探索を使える条件を見抜く」ことです。境界には単調性がありますが、2個の卵という破壊的な問い合わせ制約により、単純な半分割は最適ではありません。
まとめ
二分探索は、整列または単調性を根拠に、1回の判定で答えを含まない半分を捨てる。未整列のデータにはその根拠がない。
候補数を毎回半分にするため計算量は O(log n)。100万件でも比較は最大約20回で済む。
実装では low・high の意味とループ不変条件を保ち、比較済みの mid を次の範囲から外す。境界探索では最初の true や最後の false を探せる。
100階建てと2個の卵は、単調な境界問題でも資源制約によって二分探索が最適でなくなる例。間隔を14、13、12…と縮める戦略の最悪14回が最小。