# 二分探索法 (Binary Search)
二分探索 (にぶたん) は、**ソート済みの配列**から目的の値を `O(log n)` で見つける
アルゴリズムです。競技プログラミングでは「単調性があるか?」が、二分探索を使える
かどうかの鍵になります[^1]。
> 単調な判定関数に対して、条件を満たす境界を探す問題は、二分探索に帰着できる
> ことが多い。
## アルゴリズム
半開区間 `[lo, hi)` を毎回半分に狭めます。中央値と目標値を比較して、どちらの
半分を捨てるかを決めるだけの、シンプルな繰り返しです。
```rust
/// ソート済みスライスから target の位置を返す (なければ None)。
fn binary_search(a: &[i64], target: i64) -> Option<usize> {
let mut lo = 0usize;
let mut hi = a.len();
while lo < hi {
let mid = lo + (hi - lo) / 2; // オーバーフロー回避
if a[mid] < target {
lo = mid + 1;
} else {
hi = mid;
}
}
(a.get(lo) == Some(&target)).then_some(lo)
}
```
## 計算量
| 探索 | `O(log n)` | 毎回半分に絞る |
| 前処理 (ソート) | `O(n log n)` | 二分探索の前提 |
| ~~線形探索~~ | `O(n)` | ソート不要だが遅い |
## 学習チェックリスト
- [x] `lo + (hi - lo) / 2` でオーバーフローを防げる理由を説明できる
- [ ] 半開区間 `[lo, hi)` と閉区間 `[lo, hi]` の実装の違いを理解している
- [ ] 「答えで二分探索」(meguru 型) を自力で書ける
> [!NOTE]
> Rust の標準ライブラリには `slice::binary_search` がありますが、CP では自分で
> 書く練習が重要です。
> [!WARNING]
> 終了条件や `lo` / `hi` の更新を間違えると **無限ループ** に陥ります。境界には
> 十分注意しましょう。
### 参考リンク
- [典型 90 問 — AtCoder](https://atcoder.jp/contests/typical90)
- [二分探索 — Wikipedia](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2)