二分探索
問題
- 入力: 長さ $N$ の昇順ソート済みの配列 $a$ と探索したい値 $v$
- 出力: $a[i] = v$ となる $v$ が存在するならば $i$ を，存在しないならばその旨を返す．
アルゴリズム
使用するデータ構造
$\gdef\vleft{\mathrm{left}}$ $\gdef\vright{\mathrm{right}}$ $\gdef\vmid{\mathrm{mid}}$
- $\vleft$:「探索範囲の左端の添字を格納するための変数」
- $\vright$:「探索範囲の右端の添字を格納するための変数」
- $\vmid$:「探索範囲の中間点の添字を格納するための変数」
手続き
- $\vleft \gets 0$ と $\vright \gets (N-1)$ で各変数を初期化．
- $\vleft \leq \vright$が成立する間，以下を繰り返す:
- $\displaystyle\vmid \gets \left\lbrack \frac{\vleft + \vright}{2} \right\rbrack$ とする（注: $\lbrack x \rbrack$は$x$の小数点以下を切り捨てて整数にする関数）
- $a[\vmid]$ の値に応じて以下の通り場合分け:
- $a[\vmid] = v$ ならば，値が存在したことになるので添字 $\vmid$ を返して終了;
- $a[\vmid] < v$ ならば，$\vleft \gets (\vmid + 1)$ として 2. を繰り返す;
- $a[\vmid] > v$ ならば，$\vright \gets (\vmid - 1)$ として 2. を繰り返す．
- この部分に達した場合，配列 $a$ 中に $v$ が存在しないので，その旨を返して終了．