二分探索

デジタル大辞泉

にぶん‐たんさく【二分探索】

読み方：にぶんたんさく

《binary search》データ検索の手法の一。ソートされたデータ列から目的とするデータを検索する際、まずデータ列の中央の値と大小比較をし、目的とするデータがどちらにあるかを判断する。この作業を、目的のデータがあるとされた半分のデータ列に対して繰り返し行うことにより、目的とするデータを検索する。二分検索。バイナリーサーチ。

ウィキペディア

二分探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/03 08:05 UTC 版)

探索 > 二分探索

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

概要

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。

n個のデータがある場合、時間計算量は${\displaystyle 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ページにある）。

関連項目

• 二分探索木
• 二分法 - 二分探索のようなアイデアで方程式の近似解を求める方法

参照

1. ^ O記法では定数倍を無視できるので、単に${\displaystyle 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

表 話 編 歴 アルゴリズム
ソート	比較ソート バブルソート 選択ソート 挿入ソート シェルソート クイックソート マージソート ヒープソート シェーカーソート コムソート ノームソート 図書館ソート イントロソート 奇偶転置ソート 線形時間ソート 鳩の巣ソート 基数ソート バケットソート 並行ソート ソーティングネットワーク バッチャー奇偶マージソート シェアソート 非効率的 ボゴソート ストゥージソート グラフ トポロジカルソート
探索	リスト 線形探索 二分探索 木・グラフ 幅優先探索 最良優先探索 均一コスト探索 A* 深さ優先探索 反復深化深さ優先探索 深さ制限探索 双方向探索 分枝限定法 ビームサーチ 文字列 クヌース–モリス–プラット法 ボイヤー-ムーア法 エイホ–コラシック法 ラビン-カープ法 Bitap法
最短経路問題	ダイクストラ法 ベルマン–フォード法 ワーシャル–フロイド法
最小全域木	プリム法 クラスカル法
最大フロー問題 最小カット問題	フォード・ファルカーソン法 エドモンズ・カープ法
線型計画問題	シンプレックス法 カーマーカー法
順序統計量	選択アルゴリズム クイックセレクト 中央値の中央値
計算幾何学	凸包アルゴリズム
種類	近似アルゴリズム 乱択アルゴリズム 並列アルゴリズム 分散アルゴリズム 可積分アルゴリズム
その他	分割統治法 動的計画法 貪欲法 アルゴリズム作曲法
カテゴリ