二分探索とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > デジタル大辞泉 > 二分探索の意味・解説 

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

読み方:にぶんたんさく

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


二分探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/05/11 16:58 UTC 版)

探索 > 二分探索

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

概要

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

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

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ページにある)。

関連項目

参照

  1. ^ O記法では定数倍を無視できるので、単にとも書ける。
  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


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「二分探索」の関連用語

二分探索のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



二分探索のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの二分探索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS