二分探索 (Binary Search)

2025-08-17

二分探索の学習ノート

「半分ずつ探せばいいじゃん」って簡単に思ってたけど、実装でめちゃくちゃバグを出した。

最初に書いた間違いだらけのコード

// 初心者の頃の間違い
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length;  // ← arr.length - 1 じゃないとダメ
    
    while (left < right) {   // ← left <= right が正しい
        const mid = (left + right) / 2;  // ← Math.floor忘れた
        
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid;      // ← mid + 1 じゃないと無限ループ
        } else {
            right = mid;     // ← mid - 1 にすべき
        }
    }
    
    return -1;
}

正しい実装（やっと理解した）

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;  // 最後のインデックス
    
    while (left <= right) {      // イコールが重要！
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;       // midは違うから+1
        } else {
            right = mid - 1;      // midは違うから-1
        }
    }
    
    return -1;
}

なぜ left <= right なのか

これ、めっちゃ悩んだ。図を描いてやっと理解した：

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

1回目: left=0, right=4, mid=2, arr[2]=5 ✓ 見つかった！

でも、もしtarget=7だったら：
1回目: left=0, right=4, mid=2, arr[2]=5 < 7
2回目: left=3, right=4, mid=3, arr[3]=7 ✓

最後の瞬間：left=right=3 の時も確認が必要！

オーバーフロー問題（知らなかった）

// 実は危険な書き方
const mid = Math.floor((left + right) / 2);

// より安全な書き方（大きな数値でオーバーフローしない）
const mid = Math.floor(left + (right - left) / 2);

// JavaやC++では重要だけど、JavaScriptではそこまで気にしなくていいかも

二分探索の変形パターン

1. 最初に現れる位置を探す

function findFirst(arr, target) {
    let left = 0, right = arr.length - 1;
    let result = -1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            result = mid;
            right = mid - 1;  // 左側も探す！
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

2. 挿入位置を探す（めっちゃ使う）

function searchInsert(arr, target) {
    let left = 0, right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left;  // leftが挿入位置！
}

実践で使える場面

ソート済み配列での検索 - 当たり前だけど基本
回転ソート配列 - ちょっと工夫が必要
平方根の計算 - 実数でも二分探索できる
最小値の最大化問題 - 競プロでよく見る

デバッグのコツ（散々苦労した）

// デバッグ用のログを入れる
while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    console.log(`left=${left}, right=${right}, mid=${mid}, arr[mid]=${arr[mid]}`);
    // ...
}

小さい配列（3-5要素）で手計算して、ログと比較すると間違いが見つかりやすい。

よくある間違い（全部やった）

無限ループ: left = mid や right = mid にして進まない
配列外アクセス: right = arr.length にしてしまう
見逃し: while (left < right) で要素を見逃す
整数除算忘れ: JavaScriptでMath.floor忘れる

まとめ：二分探索マスターへの道

シンプルに見えて、バグりやすい
境界条件が超重要
図を描いて考えると理解しやすい
変形パターンも含めて練習する価値あり
O(log n) は本当に速い（100万要素でも20回程度）

次回はソートアルゴリズムについてまとめる予定

Tags: 探索効率化