整列(ソート)された一次元の配列要素から目的の値を見つけ出す方法の一つ。
逐次探索のように先頭の要素から順に比較するのではなく、まず中間の要素を調べ、
探す値との大小関係によって対象範囲を前半又は後半に縮める操作を繰り返し、範囲を狭めてゆく。
プログラム例を以下に示す。このプログラムは、配列 x[ ] 内に値 x0 が見つかった場合はその添字を返すが、見つからなかった場合はより大きな値を持つ添字を返す。
/* x[ ] は昇順整列されている。 */
/* xr は x[ ] の要素数。 x0 は捜す値。 */
int srch(int x[ ], int xr, int x0) {
int xm, xl = 0;
while (xl < xr) {
xm = (xl + xr) / 2;
if (x[xm] < x0) xl = xm + 1; else xr = xm;
}
return xl;
}
次のものは典型的な間違いの例である。 強調表示してある部分だけが異なるが、無限ループに陥ってしまう。
int xm, xl = 0;
while (xl < xr) {
xm = (xl + xr) / 2;
if (x[xm] < x0) xl = xm; else xr = xm;
}
return xl;