2分探索法
別名:バイナリサーチ
【英】binary search
2分探索法とは、検索対象がソートされている場合に適用できる高速な検索手法のことである。
2分探索法は、具体的には次のようなアルゴリズムで検索を行う。まず、検索の開始は、真ん中に位置するデータと比べる。一致すればそれで終わりである。小さければ目的のデータは前半にあり、大きければ後半にある。これをデータが無くなるまで繰り返す。
この手法の胆は、検索範囲を2分割することで、検索対象が一気に絞り込まれるところにある。1000個のデータに対しては多くても10回程度の比較により結果が得られる。一般にN個のデータから検索する場合にはlog2N回のオーダーの比較で目的とするデータが得られる。
なお、この手法はデータが整列していることが前提のため、データの変更が多い状況では、その準備のためのソートにかかる時間により、かえって全体の効率が落ちる場合がある。
二分探索
二分探索(にぶんたんさく、英: binary search、BS)やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。
概要
ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
n個のデータがある場合、時間計算量は[1]である(O記法)。
n個のデータの中央の値を見ることで、1回の操作でn/2個程度(奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個)の要素を無視することができる。
例
ソート済み配列からある値の場所を探索する例を示す。
なお、以下の各例では、探索対象の配列内に値の重複がない(配列内で2つ以上のデータが同じ値を持つことはない)ことが保証されていることとする。
データが見つかる例
下記のようなソート済み配列から25を探しだすことを考える。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果欄を設け、目的のデータがあるか否か不明な部分を「?」、データを調べた上で目的のデータが無いとわかった部分を「N」、データを調べるまでもなく目的のデータが無い部分を「n」、目的のデータがあった部分を「○」にすることにする。検索前は、以下のようになる。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果 | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? |
まず、配列の中央の位置を計算する。手計算では (最小位置 + 最大位置) / 2 でもよいが、プログラム上では 最小位置 + (最大位置 - 最小位置) / 2 とした方が安全である。(#実装上の間違いを参照。)この式を計算すると となるが、配列内の位置は整数でなければならないので、小数点以下の切り捨てまたは切り上げを行う。この記事の説明では切り捨てを採用する。床関数を使って書けば、中央位置は となる。
位置5のデータは12なので「N」となる。
位置5のデータは目的とする25より小さい。また、配列はソート済みなので、位置1から4のデータは位置5よりさらに小さいことが明らかである。よって、位置1から4まではデータを調べなくても「n」とわかる。
目的のデータはまだ「N」も「n」も付いていない位置6から10にあるかもしれない。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果 | n | n | n | n | N | ? | ? | ? | ? | ? |
位置6から10の中央の位置は となる。
位置8のデータは22なので「N」、位置6から7までは「n」とわかる。目的のデータは位置9から10にあるかもしれない。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果 | n | n | n | n | N | n | n | N | ? | ? |
位置9から10の中央の位置は となる。
位置9のデータは25なので目的のデータが見つかったことになる。位置10は調べていないが、配列内に値の重複はないという想定なので「n」としてよい。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果 | n | n | n | n | N | n | n | N | ○ | n |
データが見つからない例(1)
下記のようなソート済み配列から4を探しだすことを考える。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
配列の中央の位置は となる。
位置5のデータは12なので「N」、位置6から10まではデータを調べなくても「n」とわかる。目的のデータは位置1から4にあるかもしれない。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果 | ? | ? | ? | ? | N | n | n | n | n | n |
位置1から4の中央の位置は となる。
位置2のデータは3なので「N」、位置1も「n」とわかる。目的のデータは位置3から4にあるかもしれない。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果 | n | N | ? | ? | N | n | n | n | n | n |
位置3から4の中央の位置は となる。
位置3のデータは5なので「N」。位置4はデータを調べなくても「n」とわかる。以上で全位置が「N」または「n」と確定し、データが見つからないという結果になる。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果 | n | N | N | n | N | n | n | n | n | n |
データが見つからない例(2)
下記のようなソート済み配列から29を探しだすことを考える。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
配列の中央の位置は となる。
位置5のデータは12なので「N」、位置1から4まではデータを調べなくても「n」とわかる。目的のデータは位置6から10にあるかもしれない。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果 | n | n | n | n | N | ? | ? | ? | ? | ? |
位置6から10の中央の位置は となる。
位置8のデータは22なので「N」、位置6から7までは「n」とわかる。目的のデータは位置9から10にあるかもしれない。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果 | n | n | n | n | N | n | n | N | ? | ? |
位置9から10の中央の位置は となる。
位置9のデータは25なので「N」。目的のデータは位置10にあるかもしれない。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果 | n | n | n | n | N | n | n | N | N | ? |
位置10のデータは28なので「N」。全位置が「N」または「n」と確定したので、データが見つからないという結果になる。
位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
結果 | n | n | n | n | N | n | n | N | N | N |
コード例
int binary_search(int ary[], int key, int imin, int imax) {
if (imax < imin) {
return KEY_NOT_FOUND;
} else {
int imid = imin + (imax - imin) / 2;
if (ary[imid] > key) {
return binary_search(ary, key, imin, imid - 1);
} else if (ary[imid] < key) {
return binary_search(ary, key, imid + 1, imax);
} else {
return imid;
}
}
}
let find value (xa: 'T[]) =
let rec ifind min max =
if max < min then None
else
let c = min + (max - min) / 2
if xa.[c] > value then ifind min (c - 1)
else if xa.[c] < value then ifind (c + 1) max
else Some c
ifind 0 (xa.Length - 1)
find 8 [|1; 2; 4; 5; 6; 8; 11; 13|]
(define (find val xa)
(letrec ((ifind
(lambda (min max)
(if (< max min)
#f
(let ((c (+ min (quotient (- max min) 2))))
(cond ((> (list-ref xa c) val) (ifind min (- c 1)))
((< (list-ref xa c) val) (ifind (+ c 1) max))
(else c)))))))
(ifind 0 (- (length xa) 1))))
実装上の間違い
ドナルド・クヌースは "Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky ..."(二分探索の基本的なアイディアは比較的平易だが、その詳細は驚くほど扱いが難しいものになりうる)と述べており[2]、二分探索が正確に実装されていないことは多い。Richard E. Pattis の1988年の調査では、書籍20冊のうち15冊が誤っていた[3]。
よくある間違いの一つは、上記のC言語のコードで imin + (imax - imin) / 2 を (imax + imin) / 2 としてしまう事である。(imax + imin) / 2 では、imax + imin が int の値の上限 (INT_MAX) を超えて不正な値になってしまう可能性がある。(imax + imin が INT_MAX を超える可能性が全くないと保証できる場合は問題ない。)Java の標準ライブラリの Arrays.binarySearch() では JDK 1.2 (1998年) から間違えており、Java 6 (2006年) で修正された[4]。なお、このバグについてクヌースは、自分が気がついていなかったパターンだと、あるインタビューの際に述べている(書籍『Coders at Work』にて。オーム社から出ている邦訳では567ページにある)。
関連項目
参照
- ^ O記法では定数倍を無視できるので、単にとも書ける。
- ^ Knuth, Donald (1997). “Section 6.2.1: Searching an Ordered Table”. Sorting and Searching. The Art of Computer Programming. 3 (3rd ed.). Addison-Wesley. pp. 409–426. ISBN 0-201-89685-0
- ^ Pattis, Richard E. (1988). “Textbook errors in binary searching”. SIGCSE Bulletin 20: 190–194. doi:10.1145/52965.53012. cited at Kruse, Robert (1998). Data Structures and Program Design in C++. Prentice Hall. p. 280. ISBN 0-13-768995-0
- ^ Bug ID: JDK-5045582 (coll) binarySearch() fails for size larger than 1<<30
2分探索法と同じ種類の言葉
- 2分探索法のページへのリンク