二分探索

二分探索とは

二分探索 (Binary Search) は、ソート済み配列の中央要素と比較し、探索範囲を半分ずつ絞り込んで O(log n) で要素を検索するアルゴリズムである。線形探索の O(n) と比べて、100 万件のデータでも最大 20 回の比較で見つかる。

計算量の比較

データ件数	線形探索 (最悪)	二分探索 (最悪)
100	100 回	7 回
10,000	10,000 回	14 回
1,000,000	1,000,000 回	20 回

TypeScript での実装

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

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // 見つからない
}

binarySearch([1, 3, 5, 7, 9, 11], 7); // 3 (インデックス)

動作の流れ

配列: [1, 3, 5, 7, 9, 11, 13]  target: 9

Step 1: left=0, right=6, mid=3 → arr[3]=7 < 9 → left=4
Step 2: left=4, right=6, mid=5 → arr[5]=11 > 9 → right=4
Step 3: left=4, right=4, mid=4 → arr[4]=9 = 9 → found!

前提条件

二分探索は配列がソート済みであることが前提。ソートされていない配列には使えない。

// ❌ ソートされていない配列
binarySearch([3, 1, 7, 5, 9], 7); // 正しく動作しない

// ✅ ソート済み配列
binarySearch([1, 3, 5, 7, 9], 7); // 3

応用: lower_bound / upper_bound

// target 以上の最小インデックスを返す
function lowerBound(arr: number[], target: number): number {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

実際の利用場面

場面	説明
DB インデックス	B-Tree の各ノード内で二分探索
Git bisect	バグが混入したコミットを二分探索で特定
API のページネーション	カーソルベースのページネーション
配列の検索	Array.prototype.findIndex の高速版

git bisect

git bisect start
git bisect bad          # 現在のコミットはバグあり
git bisect good abc123  # このコミットはバグなし
# Git が中間のコミットをチェックアウト → テスト → good/bad を繰り返す
# O(log n) でバグの混入コミットを特定

基礎から学ぶなら関連書籍が手がかりになる。