《アルゴリズムを学ぶ》14.二分探索

# Overview
二分探索（Binary Search） は、ソート済みの配列 に対して高速に探索を行うアルゴリズム。
通常の線形探索に比べ、大規模なデータセットでも効率的に処理できる。
[1.二分探索の基本](#1-二分探索の基本)
[2.Python の `bisect` モジュール](#2python-の-bisect-モジュール)
[3.二分探索の応用](#3二分探索の応用)
[4.典型問題を解いてみる](#4-典型問題を解いてみる)

# 1. 二分探索の基本
### (1) 二分探索の考え方
- 配列が **ソートされていること** が前提
- 中央の要素 `mid` と `key` を比較
  `mid` が `key` より大きければ、左側を探索
  `mid` が `key` より小さければ、右側を探索
  探索範囲を半分にするので $O(log N)$ で探索可能

### (2) 二分探索の基本実装（再帰版）
```python
def binary_search(arr, key, left, right):
    if left > right:
        return -1  # 見つからなかった場合

    mid = (left + right) // 2  # 中央のインデックス
    if arr[mid] == key:
        return mid  # 見つかった
    elif arr[mid] > key:
        return binary_search(arr, key, left, mid - 1)  # 左側を探索
    else:
        return binary_search(arr, key, mid + 1, right)  # 右側を探索
```

### (3) 二分探索の基本実装（反復版）
```python
def binary_search_iterative(arr, key):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == key:
            return mid  # 見つかった
        elif arr[mid] > key:
            right = mid - 1  # 左側を探索
        else:
            left = mid + 1  # 右側を探索
    return -1  # 見つからなかった
```
- 再帰版と反復版はどちらも $O(log N)$
- 反復版の方がスタックオーバーフローのリスクがないため実用的

# 2.Python の `bisect` モジュール
Python では `bisect` を使うと、二分探索を簡単に実装できます。

```python
import bisect

arr = [1, 3, 5, 7, 9]
x = 5

index = bisect.bisect_left(arr, x)  # 5 が存在する最小の位置
print(index)  # 2
```
|関数	|説明|
|---|---|
|`bisect_left(arr, x)`	|x を挿入できる最小のインデックス|
|`bisect_right(arr, x)`	|x を挿入できる最大のインデックス|
|`insort_left(arr, x)`|x を arr にソート済みで挿入|

-`bisect_left` は二分探索の `lower_bound` に相当
-`bisect_right` は `upper_bound` に相当

# 3.二分探索の応用
### (1) 最初に出現する位置を探す（`lower_bound`）
```python
import bisect

arr = [1, 2, 2, 3, 3, 3, 4, 5]
x = 3

index = bisect.bisect_left(arr, x)  # 3 が最初に出現するインデックス
print(index)  # 3
```
- `bisect_left` を使うと 指定した値の最初の出現位置を取得

### (2) 最後に出現する位置を探す（`upper_bound`）
```python
index = bisect.bisect_right(arr, x)  # 3 の次の位置
print(index - 1)  # 5
```
- `bisect_right - 1` を使うと 指定した値の最後の出現位置を取得

# 4. 典型問題を解いてみる

### 例題1. 二分探索で値を探す
**問題: N 個の整数 A から Q 個のクエリ X に対し、X が存在するか判定せよ。**
> [参考： ABC315 B - Binary Search](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
import bisect

N, Q = map(int, input().split())
A = sorted(map(int, input().split()))

for _ in range(Q):
    X = int(input())
    idx = bisect.bisect_left(A, X)
    print("Yes" if idx < N and A[idx] == X else "No")
```
</details>

### 例題2. 最小の X を求める
**問題: N 個の整数 A がソートされている。A[i] >= X となる最小の i を求めよ。**
> [参考： ABC318 B - Lower Bound](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
import bisect

N, X = map(int, input().split())
A = sorted(map(int, input().split()))

idx = bisect.bisect_left(A, X)
print(idx if idx < N else -1)
```
</details>

### 例題3. ある範囲内の要素の個数
**問題: N 個の整数 A に対し、区間 [L, R] に含まれる要素の個数を求めよ。**
> [参考： ABC319 C - Count in Range](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
import bisect

N, Q = map(int, input().split())
A = sorted(map(int, input().split()))

for _ in range(Q):
    L, R = map(int, input().split())
    left_idx = bisect.bisect_left(A, L)
    right_idx = bisect.bisect_right(A, R)
    print(right_idx - left_idx)
```
</details>

### 例題4. 最も近い値を探す
**問題: N 個の整数 A が与えられ、各 Q 個のクエリ X に対し、最も近い値を求めよ。**
> [参考： ABC320 B - Nearest Number](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
import bisect

N, Q = map(int, input().split())
A = sorted(map(int, input().split()))

for _ in range(Q):
    X = int(input())
    idx = bisect.bisect_left(A, X)
    candidates = []
    if idx < N:
        candidates.append(A[idx])
    if idx > 0:
        candidates.append(A[idx - 1])
    print(min(candidates, key=lambda v: abs(v - X)))
```
</details>