二分探索 — ソート済み配列を半分ずつ削る

100 万件のソート済みデータから 1 件を探すのに、必要な比較回数は何回でしょうか。先頭から順に見れば最悪 100 万回です。二分探索なら 20 回です。

差を生んでいるのは「毎回、残りの半分を捨てる」という 1 つの発想だけです。

この章で学ぶこと

二分探索が探索範囲をどう狭めるか
時間計算量が O(log n)、空間計算量が O(1) になる理由
実装で踏みやすい 3 つの落とし穴
使える条件と、使えない場面

前提知識

計算量の O 記法と、対数が出る条件を前提にします。

半分ずつ捨てる

ソート済みの配列 [1, 3, 5, 7, 9, 11, 13, 15] から 7 を探します。

一発で見つかりました。もし 11 を探すなら、中央の 7 より大きいので左半分をまるごと捨てて右半分だけを見ます。捨てられるのは、配列がソート済みだから「左側には絶対にない」と言い切れるためです。

これを繰り返します。

回	探索範囲	中央の値	判断
1	`1 3 5 7 9 11 13 15`	7	11 は 7 より大きい → 右半分へ
2	`9 11 13 15`	11	一致

8 要素を 2 回で当てました。

実装

/** 昇順ソート済みの配列から target を探し、見つかればその添字、なければ -1 を返す */
function binarySearch(array: number[], target: number): number {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (array[mid] === target) {
      return mid;
    } else if (array[mid] < target) {
      left = mid + 1; // 中央より右にある
    } else {
      right = mid - 1; // 中央より左にある
    }
  }

  return -1;
}

読むうえでの要点は 3 つです。

**left と right が探索範囲を表す。**この範囲の外に答えは無い、というのが保たれ続ける条件 (不変条件) です
**left <= right が続行条件。**範囲が空になったら見つからなかったということです
**mid + 1 と mid - 1。**中央は比較済みなので範囲から外します。ここを mid のままにすると範囲が縮まらず無限ループします

計算量

時間計算量は O(log n) です。1 回のループで探索範囲が半分になるので、n 要素が 1 要素になるまでの回数が log₂ n です。

要素数	最大の比較回数
8	3
1,000	10
100 万	20
10 億	30

要素数が 1,000 倍になっても比較は 10 回増えるだけです。これが対数の効き方です。

空間計算量は O(1) です。使っているのは left / right / mid の 3 変数だけで、入力サイズが増えても増えません。入力の配列自体は追加のメモリではないので数えません。

再帰で書くと空間が変わる

同じアルゴリズムを再帰で書くと、空間計算量が O(log n) になります。

function binarySearchRecursive(
  array: number[],
  target: number,
  left = 0,
  right = array.length - 1,
): number {
  if (left > right) return -1;

  const mid = left + Math.floor((right - left) / 2);
  if (array[mid] === target) return mid;
  if (array[mid] < target) {
    return binarySearchRecursive(array, target, mid + 1, right);
  }
  return binarySearchRecursive(array, target, left, mid - 1);
}

時間計算量は反復版と同じ O(log n) ですが、呼び出しスタックが深さ log n まで積まれるぶん空間が増えます。同じアルゴリズムでも書き方で空間計算量が変わる例です。再帰の設計と、深さが問題になる条件は再帰と分割統治で扱います。

実装の落とし穴

1. 中央値の求め方

(left + right) / 2 と書くのが素直ですが、固定長整数を使う言語では left + right が桁あふれする危険があります。両方が最大値に近いと足した時点で負の数になり、添字が壊れます。

const mid = left + Math.floor((right - left) / 2); // 安全

right - left は必ず 0 以上で right を超えないので、この形なら足し算があふれません。JavaScript の数値は 64 ビット浮動小数点なので現実的な配列長では問題になりませんが、この書き方が定型として広まっているので、読めるようにしておく価値があります。

2. 境界条件

left <= right を left < right にすると、要素が 1 つ残った状態で比較されずにループを抜けます。範囲を [left, right] の閉区間として扱うなら、続行条件は <= です。

3. 範囲が縮まらない

left = mid や right = mid と書くと、mid が left と同じ値になった瞬間に範囲が変わらなくなり無限ループします。比較済みの mid は必ず範囲から外すのが原則です。

使える条件

二分探索が成立する条件は 1 つだけです。探索範囲を「答えより手前」と「答えより奥」に二分できること。

いちばん多い形が「ソート済みの配列」です。ただしそれだけではありません。

使える	使えない
昇順・降順にソート済みの配列	順序が無いデータ
添字でランダムアクセスできる構造	連結リスト (中央に一発で行けない)
「ある値以上か」で単調に判定できる問題	判定が単調でない問題

**連結リストで二分探索をしても速くなりません。**中央の要素にたどり着くまでに先頭から辿る必要があり、O(n) かかるためです。二分探索の速さは、添字で中央へ一発で飛べることに依存しています。構造ごとのアクセスコストの違いはデータ構造の選び方で扱います。

なお、探索が 1 回きりなら、ソートしてから二分探索するのは損です。ソートに O(n log n) かかるので、O(n) の線形探索より遅くなります。得をするのは、一度ソートした配列に何度も検索をかける場合です。

ソート済みでなくても使える形

「単調な判定」があれば配列でなくても使えます。

/** 条件を満たす最小の値を探す。judge は境目より手前で false、以降ずっと true */
function findBoundary(low: number, high: number, judge: (x: number) => boolean): number {
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (judge(mid)) {
      high = mid; // 条件を満たすので、これより大きい側は不要
    } else {
      low = mid + 1;
    }
  }
  return low;
}

「サーバーを何台にすれば処理時間が目標を下回るか」のように、答えの候補が並んでいて判定が単調な問題はこの形に落とせます。答えそのものを二分探索するので「答えで二分探索」と呼ばれます。

よくある誤解

「二分探索はどんな配列にも使える」 — 使えません。ソート済み (または単調な判定が可能) であることが前提です。

「二分探索の空間計算量は O(log n)」 — 反復で書けば O(1) です。O(log n) になるのは再帰で書いた場合の呼び出しスタックぶんです。

「連結リストでも二分探索すれば速い」 — 速くなりません。中央へのアクセスに O(n) かかるので、全体では線形探索と変わりません。

「探したいなら先にソートすればいい」 — 1 回だけの検索ならソートの O(n log n) のほうが高くつきます。線形探索の O(n) で十分です。

確認問題

問 1. 冒頭の binarySearch 関数の時間計算量と空間計算量を答えてください。

答え: 時間計算量 O(log n)、空間計算量 O(1)

時間: while ループが 1 周するたびに、left か right のどちらかが mid を越えて移動し、探索範囲がほぼ半分になります。範囲が n から 1 になるまでの回数は log₂ n です。

空間: 確保しているのは left / right / mid の 3 つだけで、入力サイズ n に関係なく一定です。入力の配列は追加メモリに数えません。再帰を使っていないので呼び出しスタックも積まれません。

よくある誤答が O(n) です。ループがあると反射的に線形だと思いがちですが、1 周ごとに残りが半分になるので対数になります。ループの回数ではなく、1 周で状態がどう変わるかを見てください。

問 2. 次の実装にはバグがあります。どこですか。

function buggySearch(array: number[], target: number): number {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (array[mid] === target) return mid;
    if (array[mid] < target) {
      left = mid;
    } else {
      right = mid;
    }
  }
  return -1;
}

答え: left = mid と right = mid で、範囲が縮まらず無限ループします。

要素が 2 つ残った状態を考えます。left = 0, right = 1 なら mid = 0 + Math.floor(1/2) = 0 です。

array[0] < target なら left = mid = 0 となり、left も right も変わりません
次の周回でも mid = 0 になり、同じ判定を繰り返します

mid は既に比較済みなので、必ず範囲から除外する必要があります。

left = mid + 1;   // 正しい
right = mid - 1;  // 正しい

問 3. 10 万件の配列に対して 1 回だけ検索します。「ソートしてから二分探索」と「そのまま線形探索」のどちらが速いですか。

答え: 線形探索

ソート + 二分探索 — O(n log n) + O(log n) = 実質 O(n log n)
線形探索 — O(n)

n = 10 万なら log₂ n は約 17 なので、ソートは線形探索の約 17 倍の手数です。1 回きりならソートの元が取れません。

逆転するのは検索回数が増えたときです。k 回検索するなら次の比較になります。

ソート + 二分探索 k 回 — O(n log n + k log n)
線形探索 k 回 — O(k n)

k が log n (約 17) を超えたあたりからソートが有利になります。「何回検索するか」が判断材料で、これはデータベースにインデックスを張るかどうかの判断とまったく同じ構造です。

まとめ

二分探索は探索範囲を毎回半分に捨てることで O(log n) を実現します
時間計算量 O(log n)、空間計算量 O(1) (反復で書いた場合)
再帰で書くと呼び出しスタックのぶん空間計算量が O(log n) になります
中央値は left + (right - left) / 2 の形で求めるのが定型です
mid は比較済みなので mid + 1 / mid - 1 で必ず範囲から外します。外さないと無限ループします
前提はソート済み (または単調な判定) と、中央への定数時間アクセスです
検索が 1 回だけならソートせず線形探索のほうが速くなります

次に読む

データ構造の選び方 — 二分探索が効く構造と効かない構造
再帰と分割統治 — 二分探索を分割統治の特殊形として読み直す

この章で学ぶこと​

半分ずつ捨てる​

実装​

計算量​

再帰で書くと空間が変わる​

実装の落とし穴​

1. 中央値の求め方​

2. 境界条件​

3. 範囲が縮まらない​

使える条件​

ソート済みでなくても使える形​

よくある誤解​

確認問題​

まとめ​

次に読む​