二分探索

探索 > 二分探索

二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。

概要

ソート済みのリストや配列に入ったデータ︵同一の値はないものとする︶に対する検索を行うにあたって、中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。 n個のデータがある場合、時間計算量は

O(\log _{2}n)

^[1]である︵O記法︶。 n個のデータの中央の値を見ることで、1回の操作でn/2個程度︵奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個︶の要素を無視することができる。

例

具体例を示す。

データが見つかる例

下記のようなソート済み配列から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
結果	?	?	?	?	?	?	?	?	?	?

まず、配列の中央の位置を求めると、1 + (10 - 1) / 2 = 5 除算の端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ。中央位置の計算は、手計算では (1 + 10) / 2 でもよいが、プログラム上では 1 + (10 - 1) / 2 すなわち最小位置 + (最大位置 - 最小位置) / 2 とした方が安全である。#実装上の間違いを参照。位置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の中央の位置は、6 + (10 - 6) / 2 = 8

位置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 + (10 - 9) / 2 = 9

位置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

まず、配列の中央の位置を求めると、1 + (10 - 1) / 2 = 5　︵除算の端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ︶位置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の中央の位置は、1 + (4 - 1) / 2 = 2

位置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 + (4 - 3) / 2 = 3 位置3のデータは5なので﹁N﹂。もし、データ4が存在するならば、位置3のデータ5より小さいので左になるはずである。しかし、すでにそこには存在しないことがわかっている。また、位置3より右である位置4は、データを調べていないが、位置3より大きなデータのはずなので﹁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

データの全体の一番右側が29より小さいので、データが見つからないという結果になる。

コード例

C言語

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;
        }
    }
}

F Sharp

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|]

Scheme

(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記法では定数倍を無視できるので、単に $O(\log n)$ とも書ける。
^ 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

[1] O記法では定数倍を無視できるので、単に $O(\log n)$ とも書ける。

[2] 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

[3] 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

[4] Bug ID: JDK-5045582 (coll) binarySearch() fails for size larger than 1<<30

[1]

[2]

[3]

[4]