二分探索（にぶんたんさく、、）や二分検索やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。n個のデータがある場合、時間計算量はformula_1である（O記法）。n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる。具体例を示す。下記のような配列から25を探しだすことを考える。なお、同一のデータは無いものとする。結果欄を設け、目的のデータがあるか否か不明な部分を「?」、データを調べた上で目的のデータが無いとわかった部分を「×」、データを調べるまでもなく目的のデータが無い部分を「×」、目的のデータがあった部分を「○」にすることにする。検索前は、以下のようになる。まず、配列の中央の位置を求めると、(1+10)/2=5　位置5のデータは12なので「×」、位置1～4まではデータを調べなくても「×」とわかる。目的のデータは位置6～10にあるかもしれない。位置6～10の中央の位置は、(6+10)/2=8位置8のデータは22なので「×」、位置6～7までは「×」とわかる。目的のデータは位置9～10にあるかもしれない。位置9～10の中央の位置は、(9+10)/2=9位置9のデータは25なので目的のデータが見つかったことになる。位置10は調べていないが、同一のデータは存在しないという想定なので「×」としてよい。下記のような配列から4を探しだすことを考える。なお、同一のデータは無いものとする。まず、配列の中央の位置を求めると、(1+10)/2=5　位置5のデータは12なので「×」、位置6～10まではデータを調べなくても「×」とわかる。目的のデータは位置1～4にあるかも知れない。位置1～4の中央の位置は、(1+4)/2=2位置2のデータは3なので「×」、位置1も「×」とわかる。目的のデータは位置3～4にあるかも知れない。位置3～4の中央の位置は、(3+4)/2=3位置3のデータは5なので「×」。もし、データ4が存在するならば、位置3のデータ5より小さいので左になるはずである。しかし、すでにそこには存在しないことがわかっている。また、位置3より右である位置4は、データを調べていないが、位置3より大きなデータのはずなので「×」。以上でデータが見つからないという結果になる。下記のような配列から29を探しだすことを考える。なお、同一のデータは無いものとする。データの全体の一番右側が29より小さいので、データが見つからないという結果になる。int binary_search(int ary[], int key, int imin, int imax) {ドナルド・クヌースは "Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…" と述べており、二分探索が正確に実装されていないことは多い。Richard E. Pattis の1988年の調査では、書籍20冊のうち15冊が誤っていた。良くある間違いの一つに、imin + (imax - imin) / 2 を (imax + imin) / 2 としてしまう事であり、これは、imax + imin が int の限界を超えてオーバーフローしてしまう。Java の標準ライブラリの Arrays.binarySearch() では JDK 1.2 (1998年) から間違えており、Java 6 (2006年) で修正された。

出典:wikipedia