二分探索(バイナリサーチ)入門 - O(log n) で探索範囲を半分ずつ狭める

電話帳から名前を探すとき、私たちは最初のページから1枚ずつめくったりはしません。真ん中あたりを開いて「探している名前より前か後か」を判断し、探す範囲を一気に半分に絞ります。この素朴な工夫をアルゴリズムにしたものが二分探索(バイナリサーチ, binary search)です。ソート済みのデータであれば、100万件でもわずか20回ほどの比較で目的の値にたどり着けます。この記事では、二分探索の仕組みから、JavaScriptとPythonでの正しい実装、無限ループやオーバーフローといった定番の落とし穴、そして境界を求める応用や各言語の標準ライブラリまでを、実際に動くコードとともに丁寧に整理します。前提となるソートアルゴリズム入門や、計算量の読み方をまとめた計算量とBig-O記法 入門と合わせて読むと、理解がぐっと深まります。

二分探索とは — ソート済み配列を半分ずつ狭める

配列から目的の値を探す一番素直な方法は、先頭から順に1つずつ比べていく線形探索(linear search)です。要素数を n とすると、最悪の場合は n 回の比較が必要で、計算量は O(n) です。データが増えるほど比例して遅くなります。

これに対して二分探索は、データがソート済みであることを利用します。探索範囲の真ん中の要素を見て、目的の値と大小を比べ、「目的の値は真ん中より右にある」「左にある」のどちらかを確定させます。これで残りの探索範囲は毎回ちょうど半分になります。

範囲が半分ずつ減るので、n 個の要素は「n, n/2, n/4, ...」と縮んでいき、1個になるまでにかかる回数は約 log2(n) 回です。これが二分探索の計算量 O(log n) の正体です。実際の数字で見ると差は圧倒的です。

• 要素数 100万(約 2 の 20 乗)なら、最大でも約 20 回
• 要素数 10億(約 2 の 30 乗)なら、最大でも約 30 回

線形探索なら最悪 100万回・10億回かかる探索が、二分探索では数十回で終わります。計算量の記法そのものに不安がある方は、冒頭で挙げた計算量の入門記事を先に読むと、以降の O(log n) と O(n) の比較がすっと入ってきます。

動作イメージ — 1ステップずつ追う

具体的な配列で、二分探索がどう範囲を狭めるかを追ってみます。配列 [1, 3, 4, 7, 9, 11, 15](インデックス 0 から 6)から、値 9 を探します。

範囲を閉区間 [low, high] で表し、真ん中のインデックス mid の要素と目的の値 9 を比べていきます。

7 要素の配列から、たった 3 回の比較で目的の値を見つけられました。注目したいのは、比較のたびに「見るべき範囲」が半分以下になっている点です。1 回目で範囲は 7 要素から 3 要素へ、2 回目で 1 要素へと絞られています。

基本実装 — 反復版と再帰版

まずは「値が存在するか、存在するならその位置(インデックス)を返す」素直な二分探索を書きます。見つからなければ -1 を返す方針にします。

反復版(ループ)

もっとも一般的な形です。範囲を閉区間 [low, high] で管理し、low が high を追い越したら「見つからなかった」と判断します。

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1; // 閉区間 [low, high]
 
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2); // オーバーフローに強い形
    if (arr[mid] === target) {
      return mid;      // 見つかった
    } else if (arr[mid] < target) {
      low = mid + 1;   // 目的の値は右半分にある
    } else {
      high = mid - 1;  // 目的の値は左半分にある
    }
  }
  return -1;           // 見つからなかった
}
 
console.log(binarySearch([1, 3, 4, 7, 9, 11, 15], 9)); // 4
console.log(binarySearch([1, 3, 4, 7, 9, 11, 15], 8)); // -1

mid を low + Math.floor((high - low) / 2) と書いているのは、後述するオーバーフロー対策のためです。ロジックとしては Math.floor((low + high) / 2) と同じ真ん中を指します。

再帰版

同じ処理を再帰でも書けます。探索範囲を引数で受け渡し、範囲が空(low が high より大きい)になったら終了します。

function binarySearchRec(arr, target, low = 0, high = arr.length - 1) {
  if (low > high) return -1;   // 探索範囲が空になった
  const mid = low + Math.floor((high - low) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) {
    return binarySearchRec(arr, target, mid + 1, high); // 右半分
  }
  return binarySearchRec(arr, target, low, mid - 1);    // 左半分
}
 
console.log(binarySearchRec([1, 3, 4, 7, 9, 11, 15], 15)); // 6

反復版と再帰版は計算量が同じ O(log n) です。二分探索は再帰の深さも O(log n) にとどまるため、スタックが溢れる心配はほとんどありません。好みや読みやすさで選んで構いませんが、実務では余計なオーバーヘッドがない反復版が使われることが多いです。参考までにPythonでの反復版も載せておきます。

def binary_search(arr, target):
    low, high = 0, len(arr) - 1     # 閉区間 [low, high]
    while low <= high:
        mid = (low + high) // 2     # Python の整数は桁あふれしない
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
 
print(binary_search([1, 3, 4, 7, 9, 11, 15], 9))  # 4

よくあるバグと正しい書き方

二分探索は「簡単そうに見えて正しく書くのが難しい」ことで有名です。詰まりやすい 4 点を押さえておきましょう。

1. 無限ループ

low や high の更新を mid そのものにすると、範囲が縮まずに永久にループすることがあります。閉区間 [low, high] 版では、必ず low = mid + 1 または high = mid - 1 と、mid を含まない側へ 1 つずらして更新するのが鉄則です。low = mid のように書くと、要素が 2 つ残った状態で mid が動かなくなり、ループが止まりません。

2. 区間の取り方 — 閉区間と半開区間

範囲の表し方には、両端を含む閉区間 [low, high] と、右端を含まない半開区間 [low, high) の 2 通りがあります。どちらを選ぶかで、初期値・ループ条件・更新式がセットで変わります。

大切なのは、どちらか一方に統一して混ぜないことです。閉区間のつもりで high = mid(半開区間の更新)を書いてしまう、といった取り違えが無限ループやオフバイワンの温床になります。後述する lower_bound のような境界探索では、半開区間で書くと綺麗にまとまります。

3. mid の計算とオーバーフロー

真ん中を (low + high) / 2 で求めるのは、一見すると自然です。しかしJavaやC、C++のように整数の桁数が固定の言語では、配列が非常に大きいと low + high が扱える最大値を超えてオーバーフローし、負の値になってインデックスが壊れることがあります。これを避けるため、次のように差をとってから足す形が定番です。

// 危険: low + high が桁あふれし得る(固定長整数の言語)
const midBad = Math.floor((low + high) / 2);
 
// 安全: 差をとってから足すのでオーバーフローしない
const midSafe = low + Math.floor((high - low) / 2);

JavaScriptの数値は倍精度浮動小数点数なので実用上この桁あふれはほぼ起きませんが、他言語へ移植したときのバグを防ぐ意味でも、差をとる書き方を習慣にしておくと安全です。

4. 終了条件

ループ条件は区間の定義とセットです。閉区間なら「low が high 以下の間」繰り返し、low が high を追い越した瞬間に「見つからなかった」と確定します。ここを「low が high 未満」にすると、要素が 1 つだけ残ったケースを調べ損ねます。区間・ループ条件・更新式の 3 点セットが噛み合っているかを、要素数 1 や 2 の小さな入力で一度手でなぞって確認するのがおすすめです。

応用: 境界を求める二分探索

二分探索は「値がある/ない」を調べるだけの道具ではありません。むしろ実務や競技プログラミングで多用されるのは、条件の境界を探す使い方です。

lower_bound と upper_bound

ソート済み配列に対して、次の 2 つの境界がよく使われます。

• lower_bound: 目的の値以上の要素が最初に現れる位置
• upper_bound: 目的の値より大きい要素が最初に現れる位置

重複を含む配列で「その値がいくつあるか」を数えたり、「その値を挿入すべき位置」を求めたりできます。半開区間 [low, high) で書くと綺麗です。

function lowerBound(arr, target) {
  let low = 0;
  let high = arr.length; // 半開区間 [low, high)
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (arr[mid] < target) {
      low = mid + 1; // mid は答えになり得ない
    } else {
      high = mid;    // mid は答えの候補として残す
    }
  }
  return low;        // 0 から arr.length までのいずれか
}
 
function upperBound(arr, target) {
  let low = 0;
  let high = arr.length;
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (arr[mid] <= target) { // 等しい要素も左へ寄せる
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  return low;
}
 
const a = [1, 2, 2, 2, 5, 7];
console.log(lowerBound(a, 2)); // 1  (2 が現れる最初の位置)
console.log(upperBound(a, 2)); // 4  (2 の直後の位置)
console.log(upperBound(a, 2) - lowerBound(a, 2)); // 3  (2 の個数)

lowerBound と upperBound の違いは、真ん中の値が目的の値と等しいときに左右どちらへ寄せるか、それだけです。upperBound(a, x) - lowerBound(a, x) が、その値の出現回数になります。

答えで二分探索(めぐる式二分探索)

もう一段強力な使い方が、答えそのものを二分探索する考え方です。「ある値 x について、条件を満たすか満たさないか」が x に対して単調(ある境界を境に、満たす側と満たさない側にきれいに分かれる)であれば、その境界を二分探索で求められます。探索対象は配列ではなく「答えの候補となる数値の範囲」です。

実装では、条件を満たすことが確実な値 ok と、満たさないことが確実な値 ng を用意し、両者の間を詰めていきます。競技プログラミングでは「めぐる式二分探索」の名で親しまれている書き方です。

function isqrt(n) {
  let ok = 0;     // 条件(x*x <= n)を満たすことが確実な値
  let ng = n + 1; // 条件を満たさないことが確実な値
  while (Math.abs(ok - ng) > 1) {
    const mid = Math.floor((ok + ng) / 2);
    if (mid * mid <= n) {
      ok = mid;   // 満たすので ok 側を更新
    } else {
      ng = mid;   // 満たさないので ng 側を更新
    }
  }
  return ok;
}
 
console.log(isqrt(10)); // 3  (3*3=9 は 10 以下、4*4=16 は 10 を超える)
console.log(isqrt(16)); // 4

この発想は「最小値を最大化する」「所要時間の上限を最小化する」といった最適化問題を、判定問題(その値で条件を満たせるか)に置き換えて解く、汎用性の高いテクニックです。問題を単調な判定に落とし込む視点は、アルゴリズム設計の引き出しを大きく広げてくれます。

回転ソート配列など典型問題

ソート済み配列をある位置で回転させた回転ソート配列(例: [4, 5, 6, 7, 0, 1, 2])からの探索も、二分探索の定番応用です。真ん中で分けたとき、左右どちらか一方は必ずソート済みになっている、という性質を使います。

function searchRotated(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (arr[mid] === target) return mid;
    if (arr[low] <= arr[mid]) {          // 左半分がソート済み
      if (arr[low] <= target && target < arr[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    } else {                             // 右半分がソート済み
      if (arr[mid] < target && target <= arr[high]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }
  return -1;
}
 
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0)); // 4

このほか、「条件を満たす最初の位置を探す」形は、単調に変化するデータ全般に応用できます。探索という切り口では、グラフ上を辿るグラフ探索アルゴリズム入門とも地続きで、あわせて眺めると探索の全体像が見えてきます。

標準ライブラリの二分探索

自分で書けることは大切ですが、実務では言語が用意した実装を使うほうが安全で確実です。主要言語の関数を、戻り値の仕様まで正確に押さえておきましょう。

Python(bisect モジュール)

標準ライブラリの bisect が、まさに lower_bound / upper_bound に対応します。

• bisect_left(a, x): 挿入位置を返す。x があれば既存要素の左を指す。a[:i] がすべて x 未満、a[i:] がすべて x 以上になる位置(lower_bound 相当)
• bisect_right(a, x)(別名 bisect): a[:i] がすべて x 以下、a[i:] がすべて x より大きい位置(upper_bound 相当)
• insort_left / insort_right: 探索した位置へ実際に挿入して並びを保つ(戻り値なし、リストを直接更新)

from bisect import bisect_left, bisect_right
 
a = [1, 2, 2, 2, 5, 7]
print(bisect_left(a, 2))   # 1  (2 が現れる最初の位置)
print(bisect_right(a, 2))  # 4  (2 の直後の位置)
print(bisect_right(a, 2) - bisect_left(a, 2))  # 3  (2 の個数)
 
# bisect は「位置」を返すだけなので、存在判定は自分で確認する
i = bisect_left(a, 5)
print(i < len(a) and a[i] == 5)  # True

bisect_left は「見つかったか」ではなく「挿入すべき位置」を返す点に注意してください。存在を確かめたいときは、返ってきた位置の要素が本当に目的の値と等しいかを自分で確認します。

C++(algorithm ヘッダ)

• std::lower_bound: 指定した値以上(未満ではない最初)の要素を指すイテレータを返す
• std::upper_bound: 指定した値より大きい最初の要素を指すイテレータを返す
• std::binary_search: 値が存在するかを bool で返す
• std::equal_range: lower_bound と upper_bound の組を一度に返す

いずれもソート済みの範囲が前提です。ランダムアクセス可能なイテレータ(std::vector など)に対して O(log n) で動きます。

#include <algorithm>
#include <vector>
#include <iostream>
 
int main() {
    std::vector<int> a = {1, 2, 2, 2, 5, 7};
    auto lo = std::lower_bound(a.begin(), a.end(), 2); // 2 以上の最初
    auto hi = std::upper_bound(a.begin(), a.end(), 2); // 2 より大きい最初
    std::cout << (lo - a.begin()) << "\n"; // 1
    std::cout << (hi - a.begin()) << "\n"; // 4
    std::cout << (hi - lo) << "\n";        // 3  (2 の個数)
    std::cout << std::binary_search(a.begin(), a.end(), 5) << "\n"; // 1 (true)
}

Java(Arrays / Collections)

• Arrays.binarySearch(配列, key): 見つかればそのインデックスを返す。見つからなければ -(挿入位置) - 1 を返す。挿入位置は「key より大きい最初の要素の位置」または末尾
• Collections.binarySearch(リスト, key): List に対して同じ仕様

戻り値が 0 以上なら見つかった、負なら見つからなかった、という約束です。見つからなかったときの負の値から -(戻り値) - 1 を計算すると、挿入すべき位置が得られます。配列はソート済みである必要があり、同じ値が複数あるときにどのインデックスが返るかは保証されません。

import java.util.Arrays;
 
int[] a = {1, 3, 4, 7, 9};
int found = Arrays.binarySearch(a, 7); // 3 (見つかった位置)
int miss  = Arrays.binarySearch(a, 5); // -4 = -(挿入位置 3) - 1
int insertionPoint = -(miss) - 1;      // 3 (5 を入れるべき位置)

JavaScript

JavaScriptには、標準の二分探索関数は用意されていません。Array.prototype.indexOf / includes / find / findIndex はいずれも先頭から順に走査する O(n) の線形探索です。ソート済みデータで O(log n) の探索が欲しい場合は、本記事のように自分で実装するか、ライブラリを使う必要があります。

使いどころと注意

二分探索は強力ですが、万能ではありません。採用を判断するときの勘所を整理します。

• ソート済みが大前提: 未ソートなら、まず並べ替えるコスト O(n log n) がかかります。1 回並べ替えて何度も探索するなら、ソートコストは複数回のクエリで償却できて割に合います。逆に 1 回きりの探索のためだけに並べ替えるなら、O(n) の線形探索のほうが速いこともあります
• 完全一致だけならハッシュのほうが速いことも: 「この値があるか」を平均 O(1) で調べたいだけなら、ハッシュテーブル入門で扱うハッシュ集合が有利です。一方でハッシュは順序を保たないため、「x 以上の最小の要素」「範囲内の件数」といった順序や範囲にまつわるクエリは苦手です。ここは二分探索(やソート済み構造)の独壇場です
• データベースの索引も同じ発想: RDBがインデックスに使うB木は、各ノードで探索範囲を絞りながら木を降りていく、二分探索を多分岐に拡張したような構造です。仕組みはデータベースのインデックス入門で解説しています
• 頻繁な挿入・削除があるなら別の構造も検討: ソート済み配列は探索に強い一方、途中への挿入・削除に O(n) かかります。更新が多いなら、平衡二分探索木のような順序付きの木構造が向きます

まとめると、「順序に意味があり、並べ替えのコストを複数回の探索で回収できる」場面が二分探索の得意分野です。

まとめ

• 二分探索はソート済みデータの探索範囲を毎回半分に狭め、O(log n) で目的の値へたどり着く。100万件でも約 20 回で済む
• 実装は反復版と再帰版があり計算量は同じ。区間の取り方(閉区間 [low, high] か半開区間 [low, high) か)と、ループ条件・更新式の 3 点セットを統一するのが正しく書くコツ
• 定番の落とし穴は無限ループ、区間の取り違え、mid のオーバーフロー、終了条件の 4 つ。mid は low + (high - low) / 2 で求める習慣をつける
• 応用として lower_bound / upper_bound による境界探索、条件を判定問題に落とす「答えで二分探索」、回転ソート配列の探索がある
• 標準ライブラリはPythonの bisect、C++の lower_bound / upper_bound、Javaの Arrays.binarySearch が定番。JavaScriptには標準の二分探索がなく自前実装が必要
• ソートコストやクエリの種類(完全一致か範囲か)を踏まえ、ハッシュテーブルなど他の手段と使い分ける

まずは閉区間の反復版を、要素数 1 と 2 の小さな入力で手でトレースしながら確実に書けるようにしてみてください。そこさえ固まれば、境界探索も「答えで二分探索」も、同じ骨格の応用として自然につながっていきます。

参考リンク

• Binary search algorithm - Wikipedia
• bisect — Array bisection algorithm — Python 公式ドキュメント
• std::lower_bound - cppreference.com
• Arrays.binarySearch - Java Platform SE ドキュメント