二分探索 — Project Hematite

10 億要素のソート済み配列で値を見つけるために左から右へスキャンすると、10 億回の比較が必要になることもある。二分探索はソート済みの順序を利用して同じ仕事を最大 30 回の比較で行う — 各ステップで残りの候補を半分にすることで。これを深く理解することは、より広く役立つことも教えてくれる：ループを正確な不変条件の周りで書くことで、正しさを推測ではなく明らかにする方法だ。

アイデア：探索空間を半分にする

ソート済み配列があり、ある target 値がその中にあるかどうか、あるなら何番目のインデックスにあるかを知りたいとする。真ん中の要素を選ぶ。3 つのことが起こりうる：

target と等しい — 完了。
より小さい — 配列がソートされているので、mid の左にある要素はすべて target より小さい。左半分を完全に捨てられる。
より大きい — 同じ論理で、右半分を捨てる。

各比較で候補数が半分になる。 $n$ 要素から始まって $k$ ステップ後には最大 $\lceil n / 2^k \rceil$ が残る。ターゲットが見つかるか残った区間が空になったとき終了し、それは最大 $\lceil \log_2 n \rceil$ ステップ後だ。 $O(\log n)$ はここから来る。

不変条件

二分探索で最も難しいのはアイデアではなく、境界の更新を一貫に保つことだ。最もクリーンなアプローチは半開区間（half-open interval） $[\mathtt{lo}, \mathtt{hi})$ を使う：ターゲットの候補はインデックス $i$ （ $\mathtt{lo} \le i < \mathtt{hi}$ ）にある要素のみだ。

この区間には 3 つの便利な性質がある：

配列全体から始まる：lo = 0、hi = arr.len。
lo == hi のとき正確に空になる — ループ終了条件だ。
すべての更新が不変条件を保持しなければならない — 更新後もターゲット（存在すれば）が新しい区間の中に存在する。

mid = lo + (hi - lo) / 2 を計算した後の更新は以下のようになる：

arr[mid] < target のとき：mid とその左にあるものはすべて小さすぎる。新しい探索空間は $[\mathtt{mid}{+}1, \mathtt{hi})$ なので lo = mid + 1 とする。
arr[mid] > target のとき：mid とその右にあるものはすべて大きすぎる。新しい空間は $[\mathtt{lo}, \mathtt{mid})$ なので hi = mid とする。

どちらの場合も区間は厳密に縮小し（この重要性はすぐわかる）、不変条件は保持される。

トレース例

配列：[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]、ターゲット：23。

ステップ	`lo`	`hi`	`mid`	`arr[mid]`	行動
1	0	10	5	23	発見！

運良く 1 ステップ。ターゲット 16 を試す：

ステップ	`lo`	`hi`	`mid`	`arr[mid]`	行動
1	0	10	5	23	23 > 16、hi = 5 に設定
2	0	5	2	8	8 < 16、lo = 3 に設定
3	3	5	4	16	発見！

そして不在のターゲット 17：

ステップ	`lo`	`hi`	`mid`	`arr[mid]`	行動
1	0	10	5	23	23 > 17、hi = 5 に設定
2	0	5	2	8	8 < 17、lo = 3 に設定
3	3	5	4	16	16 < 17、lo = 5 に設定
4	5	5	—	—	lo == hi、未発見

Zig での実装

const std = @import("std");

// `arr` の中から `target` のインデックスを返す。存在しない場合は null。
// `arr` は昇順でソートされていなければならない。
fn binarySearch(arr: []const i32, target: i32) ?usize {
    var lo: usize = 0;
    var hi: usize = arr.len;

    while (lo < hi) {
        const mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return null;
}

pub fn main() void {
    const data = [_]i32{ 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };

    if (binarySearch(&data, 23)) |idx| {
        std.debug.print("found 23 at index {}\n", .{idx}); // found 23 at index 5
    }

    if (binarySearch(&data, 17)) |_| {
        std.debug.print("found 17\n", .{});
    } else {
        std.debug.print("17 not found\n", .{}); // 17 not found
    }
}

注目すべき点：

mid = lo + (hi - lo) / 2 を (lo + hi) / 2 の代わりに使う。素朴な形は lo + hi が usize の最大値を超えるとオーバーフローするが、この形はしない。
関数は ?usize、Zig のオプション型を返す。呼び出し元は if (result) |idx| { ... } else { ... } で両方の結果を処理する。
配列パラメータは []const i32 — 変更を許可しないスライスだ。

すべてを破壊するオフバイワンミス

二分探索のオフバイワンエラーは非常に一般的だ。各ミスが何をするかを知っていると、素早く発見して修正できる。

閉区間で `lo <= hi` を使う

実装によっては閉区間 $[\mathtt{lo}, \mathtt{hi}]$ を使い while (lo <= hi) と書く。これは境界の更新も lo = mid + 1 および hi = mid - 1 に変更する場合のみ一貫している。閉区間のループと半開区間の境界更新を混在させる（- 1 を忘れる）と無限ループが発生する：ターゲットが不在で lo == hi のとき、hi = mid を計算すると hi = lo のままになり、区間が空にならない。

半開スタイルで `hi = mid - 1` と書く

半開スキームでは hi は排他的上界 — 決して参照されないインデックスだ。arr[mid] > target のとき hi = mid - 1 とすると、根拠なく mid - 1 を探索空間から除外する。ターゲットがインデックス mid - 1 にある場合、見逃す。

`lo = mid + 1` の代わりに `lo = mid` と書く

arr[mid] < target のとき mid は答えではないとわかる。lo = mid とすると mid が区間内に残る。さらに悪いことに、hi = lo + 1 のとき mid は lo に計算され、lo = mid = lo の更新で lo が変わらず — ループが永遠に止まらない。

覚えるパターン：各更新は新しい区間から mid を除外しなければならない。半開スキームはこれを自然に達成する：lo = mid + 1 と hi = mid はどちらも mid を $[\mathtt{lo}, \mathtt{hi})$ の外に残す。

ループが必ず終了する理由

区間は必ず縮小するか？半開スキームでは：

lo = mid + 1 は lo を少なくとも 1 増やす（mid >= lo なので）。
hi = mid は hi を少なくとも 1 減らす（lo < hi のとき mid < hi だから）。

早期 return しない各反復で hi - lo が厳密に減少する。hi - lo は非負整数で毎ステップ減少するため、ループは必ず終了する。

まとめ

二分探索は各ステップで探索区間を半分にすることでソート済み配列からターゲットを $O(\log n)$ 時間で見つける。
半開区間 $[\mathtt{lo}, \mathtt{hi})$ を使う：不変条件は「ターゲットが存在すればこの範囲のインデックスにある」だ。ループは lo < hi の間実行される。
整数オーバーフローを避けるため中点は lo + (hi - lo) / 2 で計算する。
境界の更新 lo = mid + 1 と hi = mid はどちらも新しい区間から mid を除外し、不変条件を保持して終了を保証する。
オフバイワンエラーは非互換な区間スタイルの混在、または探索空間内に mid を残して無限ループを作る更新から生じる。
$O(\log n)$ 境界は区間が各ステップで半分になることから来る： $k$ ステップ後には最大 $\lceil n/2^k \rceil$ の候補が残る。