二分探索 (反復版)｜コードで実践

二分探索 (反復版)

このレッスンで分かること

ソート済み配列に対しては、線形探索ではなく二分探索を選ぶのが鉄則です

二分探索 は ソート 済みの配列に対して使える、計算量 O(log n) の超高速な探索アルゴリズムです

探索区間の 中央 を見て、目的の値より大きいか小さいかで 左半分 か 右半分 のどちらかに絞り込んでいきます

二分探索とは

ソート済み配列に対し、while ループで区間を半分ずつ狭めていく二分探索を反復で実装します。本レッスンでは、二分探索の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

二分探索 は ソート 済みの配列に対して使える、計算量 O(log n) の超高速な探索アルゴリズムです。線形探索 が O(n) だったのに比べ、n = 10^6 なら 20 回ほどの比較で答えが出ます。

ソート済み配列に対しては、線形探索ではなく二分探索を選ぶのが鉄則です。

仕組み

探索区間の 中央 を見て、目的の値より大きいか小さいかで 左半分 か 右半分 のどちらかに絞り込んでいきます。区間長は毎回半分になるので、n から 1 までに減らすのに必要なステップ数は log2(n) 回です。

diagram (will load when visible)

反復版コード

Python

def binarySearchIter(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

JavaScript

function binarySearchIter(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor(low + (high - low) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

よくある実装ミス

二分探索は短いコードですが、境界条件 が間違いやすいことで有名です。代表的なバグは次の通りです。

low + high で オーバーフロー する (Java の int で n が大きいときに注意)
mid = low + (high - low) // 2 と書くのが安全
low <= high ではなく low < high にしてしまい、1 要素のケースを取りこぼす
low = mid high = mid にしてしまい、無限ループ に陥る
配列が ソート されていないのに二分探索を使ってしまう

二分探索のバグの大半は「区間の閉じ方」と「mid の更新」にあります。

計算量

n	必要な比較回数 (log2)
`8`	`3`
`1024`	`10`
`10^6`	`約 20`
`10^9`	`約 30`

線形探索が O(n) であることを考えると、n = 10^9 で 30 回程度の比較というのは桁違いの速さです。電話帳 辞書 データベースのインデックス など、現実世界の探索処理の多くが二分探索 (または B-tree などの拡張) の上に成り立っています。

反復版と再帰版の違い

二分探索には 再帰版 もあります (次のレッスンで扱います) が、現実のコードでは 反復版 の方が好まれます。

反復版は スタック を消費しない (再帰 だと O(log n) のスタック)
ループの方が デバッグ しやすい
末尾再帰最適化 がない言語 (Python Java 等) ではどちらにせよ スタック を消費する

標準ライブラリの bisect (Python) や Arrays.binarySearch (Java) も内部は反復版です。

やってみよう

配列 [1, 3, 5, 7, 9, 11] から 7 を探すと index = 3、4 を探すと -1 を返します。区間 low / high の動きを紙に書きながら追うと、二分探索の感覚がつかみやすいです。

本レッスンでは 反復版 のみを実装します。while の条件と mid の更新を間違えないことを意識してください。

学習のコツ

二分探索は短いコードですが、境界条件 の組み合わせが多いので、紙に low high mid の遷移を書き出すと頭に残りやすいです。要素 1 個 要素 2 個 target が先頭 target が末尾 target がない の 5 つのケースをすべて手でなぞってみてください。

要素 1 個 (arr=[5], target=5): low=0, high=0、mid=0、arr[mid]==target で return 0
要素 1 個 で見つからない (arr=[5], target=3): mid=0、arr[mid] > target なので high=-1、ループ抜けて return -1
target が先頭 (arr=[1,3,5,7], target=1): mid=1、arr[mid]=3>1 なので high=0、次に mid=0、arr[0]=1 で return 0
target が末尾: mid がだんだん右に寄り、最後に末尾の index を返す
target がない: low > high でループを抜け return -1

5 ケースを暗算でなぞれるようになったら、二分探索 は完全に身についたと言えます。

業務でも Array.prototype.findIndex で十分な場面と、二分探索 を使うべき大規模 ソート済みデータ の場面がはっきり分かれます。データベースのインデックス B-tree スパースインデックス などの内部構造も二分探索の考え方を発展させたものです。

よくある質問

Q. 二分探索の前提は何ですか？

A. 配列がソート済みであることです。未ソートだと結果が保証されません。実行前に Arrays.sort や sorted を呼んでから二分探索するか、最初からソート済みのデータ構造（TreeSet / SortedDict）を使ってください。

Q. 再帰版と反復版はどっちが良いですか？

A. 反復版が安定して高速です。再帰版は読みやすい代わりにスタック消費があります。配列の長さが極端に大きい（数億）場合のみ反復版を選び、教育用や読みやすさ重視なら再帰版で十分です。Python は再帰深さ制限にも注意してください。

Q. lower_bound / upper_bound とは何ですか？

A. lower_bound は target 以上が最初に現れる位置、upper_bound は target より大きい値が最初に現れる位置を返します。重複要素のある配列で「何個含まれているか」を upper - lower で求める典型イディオムで使います。

次のレッスン

次は 二分探索 (再帰版) で、ソート済み配列に対し、while ループで区間を半分ずつ狭めていく二分探索を反復で実装しますを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

二分探索 (反復) の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 二分探索 (反復) とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

二分探索 (反復版)