サムネイル|300ピクセル|二分探索アルゴリズムの視覚化。探索目標値は7である。 二分探索（）もしくはバイナリサーチとは、計算機科学においての中から目標の値の位置を見つけ出す探索アルゴリズム。このアルゴリズムでは、探索目標と、配列の中央に位置する要素とをまず比較する。値が等しくない場合、目標が存在する可能性がない側の半分の部分配列を除外し、残りの半分について中央要素との比較を再び行う。この手続きを目標値が見つかるまで繰り返す。配列が空になって終了したなら、元の配列に目標値が存在しなかったということである。
二分探索はで動作するアルゴリズムであり、最悪のケースにおいて比較演算を 回行う（ は配列の要素数）。二分探索は配列が特に小さくなければ線形探索より高速であるが、実行するには配列があらかじめソートされていなければならない。ハッシュテーブルのように探索速度に特化したデータ構造ならば二分探索よりも効率よく探索を行うことができるが、二分探索は配列に目標の値が含まれない場合に最近傍の値を見つけるような応用がある。
二分探索には多くの変種がある。そのうちは、複数の配列に対して同じ値の二分探索を行う高速な手法であり、計算幾何学など多くの分野における探索問題を効率的に解くことができる。は二分探索を無限長のリストに拡張したものである。二分探索木やB木といったデータ構造は二分探索に基づいている。
アルゴリズム 二分探索は整列配列に対して用いられる。まず配列の中央の要素と探索対象の値を比較し、一致している場合はその位置を返す。探索対象が中央要素より小さかったなら、配列の前半部に対して同じ手続きを行う。探索対象が中央の要素より大きかったなら後半部で探索をする。このように、各回の反復において、配列を二つに分けて探索対象が存在しないとわかった側の領域を除外していく。
手続き 長さ の配列 があり、要素の値もしくはレコード は のようにソートされているとする。また探索目標値を とする。以下のサブルーチンは二分探索によって 内の要素 のインデックスを求める。
変数 に を、 に を代入する。 ならば探索は失敗して終了する。 配列 の中央要素の位置を表す変数 に を代入する。床関数 は引数 以下の最大の整数を与える。 ならば に を代入し、ステップ2に戻る。 ならば に を代入し、ステップ2に戻る。 となったら探索は完了する。 の値を返す。
この反復手続きは探索範囲を変数 および によって管理している。擬似コードで表すと以下のようになる。変数名と型は上記と同じであり、floor は床関数、unsuccessful は探索が失敗したことを表す変数値である。 右|サムネイル|二分探索の手順。 function binary_search(A, n, T) is L := 0 R := n − 1 while L ≤ R do m := L + floor((R - L) / 2) if A[m] < T then L := m + 1 else if A[m] > T then R := m − 1 else: return m return unsuccessful に対して床関数ではなく天井関数を用いるアルゴリズムもある。その場合、探索目標の値が配列内に複数存在するとき結果が変わる可能性がある。
代替手法 上記の手続きでは、中央の要素 () が目標値 () と等しいかの判定を毎回の反復ごとに行っている。一部の実装では、この比較を反復の中では行わず、要素が1つだけ残ったとき（になったとき）にのみ実行する。これにより、反復中の比較処理が1回減るためループが高速化されるが、反復回数は平均で1回増えるだけで済む Procedure is described at p. 214 (§43), titled "Program for Binary Search".。以降ではこの方法を「代替手法」と呼ぶ。
は1962年に等価判定を省略する実装を最初に公開した。
に を、 に を代入する。 である間、以下を繰り返す。 中央要素の位置 に を代入する。天井関数 は 以上の最小の整数を与える。 であるならば、 に を代入する。 そうでないならば である。 に を代入する。 となった時点で探索完了。 ならば を返す。そうでなければ、目標値が見つからずに終了したことになる。
このバージョンの疑似コードは以下のようになる。 function binary_search_alternative(A, n, T) is L := 0 R := n − 1 while L != R do m := L + ceil((R - L) / 2) if A[m] > T then R := m − 1 else: L := m if A[L] = T then return L return unsuccessful
重複要素 配列内に重複する要素が存在する場合、この手続きは任意の目標値と等しい要素のインデックスを返す。たとえば、探索対象の配列が 、目標値が であれば、第4要素（インデックス3）と第5要素（インデックス4）のいずれを返してもアルゴリズムは正しく機能している。床関数を用いる手続きであれば第4要素を返す。重複要素の左端が常に返ってくるわけではなく、 のような配列でも第4要素が返される。場合によっては、配列内で目標値が重複しているときその中の左端もしくは右端の要素を見つける必要がある。 の例では、目標値 を持つ要素のうち第4要素が左端、第5要素が右端である。等価比較を省略する代替手法は、配列中に目標値が存在するならば常に右端の要素を返す。
左端の要素を探索する手続き 以下の手続きによれば目標値と等しい要素の左端を見つけることができる。
に を、 に を代入する。 である間、以下を繰り返す。 中央要素の位置 を とする。 ならば に を代入する。 そうでないならば である。 に を代入する。 を返す。
かつ であれば、 が に等しい要素の左端である。 が配列に含まれなかったとしても、 は配列 における の順位（ より小さい要素の数）を表している。
このバージョンの疑似コードは以下になる。 function binary_search_leftmost(A, n, T): L := 0 R := n while L < R: m := L + floor((R - L) / 2) if A[m] < T: L := m + 1 else: R := m return L
右端の要素を探索する手続き 以下の手続きで右端の要素を見つけることができる。
に を、 に を代入する。 である間、以下を繰り返す。 中央要素の位置 に を代入する。 ならば に を代入する。 そうでないならば である。 に を代入する。 を返す。
かつ であれば、 が に等しい要素の右端である。 が配列に含まれなかったとしても、 は配列 のうち より大きい要素の数を表している。
疑似コードは以下の通りである。 function binary_search_rightmost(A, n, T): L := 0 R := n while L < R: m := L + floor((R - L) / 2) if A[m] > T: R := m else: L := m + 1 return R - 1
近似一致 サムネイル|350ピクセル|二分探索は近似一致の計算にも応用できる。探索対象値の5が配列中に存在しない場合にも二分探索によって順位 (Rank)、直前要素 (Predecessor)、直後要素 (Successor)、最近接要素 (Nearest neighbor) が取得できる。 上記の手続きは完全一致の判定のみを行って目標値の位置を見つけるものである。しかし、二分探索は整列配列を対象としているため、近似一致の判定を行うように拡張することは容易である。たとえば、与えられた値に対して、順位（より小さい要素の数）、直前要素（次に値が小さい要素）、直後要素（次に値が大きい要素）、最も近い要素を求めるなどである。2つの値について順位を求めることで、それらの間にある要素数を求めるも実行可能である。
順位クエリは左端要素を求める手続きによって実行できる。 直前要素クエリは順位クエリによって実行できる。目標値の順位が なら、直前要素のインデックスは である。 直後要素クエリは右端要素を求める手続きによって実行できる。返ってきたインデックスが なら、直後要素は である。 目標値の最近傍要素は、直前要素と直後要素のうち目標値に近い方である。 範囲クエリも容易に行うことができる。2つの値の順位を求めて差をとれば、大きい方の値未満で小さい方の値以上の要素数になる。端点を範囲に含めるかどうか、また配列に端点に等しい要素が存在するかどうかによって求めた数を1ずつ増減して調整する。
性能 サムネイル|200ピクセル|二分探索を表す木構造。ここで探索対象となっている配列は 、探索目標値は である。 サムネイル|400ピクセル|二分探索の最悪ケースでは、木構造の探索が最も深いレベルに到達する。最良ケースとなるのは目標値が配列の中央要素と一致したときである。 二分探索の性能のうち比較回数に関する部分は、手続きを二分探索木で表すことで評価できる。二分探索木の根ノードは配列の中央要素である。その子ノードは、左側が配列の前半の中央要素、右側が後半の中央要素となる。それ以降も同様に構築される。探索は根ノードから開始され、現在のノードの値を目標値と比較して大小に応じて左右の部分木をたどっていく。
最悪の場合、二分探索は比較ループを 回反復する。 は引数以下の最大の整数を返す床関数、 は二進対数である。二分探索木の階層数は常に になり、その最深層に到達するのが最悪ケースにあたる。
目標の要素が配列内に存在しないならば、場合によって最悪ケースとなる。 が2のべき乗から1を引いた値であれば常にこれが当てはまる。それ以外の配列長では、反復数 回で探索木の最深層に到達することもあり、反復数 回（最深層より一つ上）で探索が終了することもある。
全要素が等しい確率で探索対象となるとして反復回数を平均すると、目標要素が配列内に存在する場合には 回となる。これは 回におよそ等しい。目標要素が配列内に存在しない場合、目標要素の挿入位置が両端も含めた要素間の中から等確率で選ばれるならば、反復回数は回となる。
最良ケースとなるのは目標値が配列の中央要素と一致している場合で、反復1回のみでその位置が返される。
反復回数の点では、要素同士の比較のみに基づく探索アルゴリズムのうち、平均および最悪ケースにおいて二分探索より優れた性能を示すものは存在しない。二分探索を表す比較木は最下層を除くすべての階層が完全に埋まっているため、階層数は限界まで最小化されている。木構造がそれ以外のものになると、1回の反復で除外できる要素数が減ることになるため、平均および最悪ケースでの反復回数が増える。このため、二分探索以外の比較ベースのアルゴリズムは、特定の目標値に対しては二分探索より速い場合があるとしても、すべての要素にわたって平均した性能では劣る。二分探索は配列を二分割することで部分配列のサイズを可能な限り均等に保っている。
空間計算量 二分探索では、配列の大きさにかかわらず、要素を指定するためのポインタ（配列インデックス、もしくはメモリ位置へのポインタ）を3つ必要とする。すなわち、モデルにおいて二分探索のは である。
平均ケースの導出 二分探索における平均の反復回数は、探索対象がどのような確率で選ばれるかに依存する。また探索が成功する場合と失敗する場合でも異なる。ここでは、成功する場合については、すべての配列要素が等確率で探索対象になると仮定する。失敗する場合では、すべての要素間および両端の外の各区間が等確率で選ばれるとする。成功時の平均ケースは、すべての要素を一度ずつ探索したときに必要な反復回数の合計を要素数 で割ったものである。失敗時の平均ケースは、各区間で一度ずつ探索を行ったときの反復回数の合計を区間数 で割ったものである。
探索対象が見つかる場合 二分木表現において、探索対象が見つかる場合の探索は根から目標ノードまでのパスとして表される。これを内部パス (internal path) と呼ぶ。パスの長さは含まれるエッジ（ノード間の接続）の数で与えられる。パス長を とすれば、その探索の反復回数は初回の比較を含めて 回となる。すべての内部パスの長さの合計を内部パス長 (internal path length) とする。各ノードには根からのパスが一意に存在するため、一つの内部パスが一つの要素を対象とする探索を表すことになる。要素の数が正整数 であり、かつ内部パス長が なら、探索が成功する場合の反復回数の平均は で与えられる。加算されている1はすべての探索で必要になる初回の比較を表す。
二分探索は比較に基づく探索アルゴリズムとして最適であるため、探索成功時の平均反復回数は、ノード数 のあらゆる二分木のうち最小の内部パス長を求める問題に帰着する。その値は以下で与えられる。
たとえば要素数7の配列では、根ノードが表す探索は反復回数が1回のみであり、根の下に位置する2要素はそれぞれ2回、その下の4要素はそれぞれ3回の反復を必要とする。この場合の内部経路長は以下である。
平均の反復回数は となる。
の総和は以下のようにも書き換えられる。
この を の式に代入すると以下が得られる。
が整数であれば、上式は、成功する探索について先に述べた平均ケースの式と等価である。
探索対象が見つからない場合 配列中に目標値が見つからないような探索は、木構造に外部ノード (external nodes) を追加することで表現できる。そのようにして得られる木を拡張二分木 (extended binary tree) と呼ぶ。内部ノード（木に元々含まれていたノード）すべてについて、子ノードを2つ未満しか持たないならば外部ノードを子として追加することで子を必ず2つ持つようにする。これにより、失敗する探索は一つの外部ノードへのパスとして表される。その外部ノードの親は、探索中の最後の反復で残った配列要素に対応する。根から外部ノードに至る経路を外部パス (external path)、すべての外部パスの長さの総和を外部パス長 (external path length) と呼ぶ。要素数が正整数 、外部パス長が であれば、目標値が見つからない探索における平均反復回数は、最初の反復を含めて となる。外部パス長が ではなく で割られているのは、配列の各要素の間、および両端に存在する区間に対応して 個の外部経路が存在するためである。
目標値が見つかる探索の場合と同様に、この問題もノード数 のあらゆる二分木のうち最小の外部パス長を求める問題に帰着する。いかなる二分木も外部パス長は内部パス長より だけ多いので、 の式を代入して
となる。この を に代入することで、探索が失敗する場合の平均ケースを求められる。
代替手法の性能 本項の初めに定義した二分探索の手続きでは、毎回の反復で中央要素が探索目標と等しいかをチェックする。比較回数は反復ごとに1回もしくは2回であり、すべての要素が等しい確率で探索されるならば平均して反復ごとに1.5回となる。それに対し、すべての反復が終わった後に残った要素に対して1回だけ探索目標と等しいかのチェックを行う代替手法では、反復ごとに平均で0.5回の比較が省略できる。そのかわりに必ず最大の回数の反復が行われるため、反復回数は1つの探索につき平均1回増加してしまう。比較ループは最悪ケースでも 回しか行われないため、反復ごとの効率がわずかに上昇するとしても、 が非常に大きい場合を除けば余分な1回の反復を埋め合わせるには十分ではない。
実行時間とキャッシュ使用 二分探索の性能評価では要素の比較に要する時間も考慮の対象となる。整数や文字列の比較時間は通常そのエンコーディング長（多くの場合ビット数）に比例して増加する。たとえば、64ビット符号なし整数同士の比較であれば、32ビットの場合と比べて最大で2倍のビット数を比較する必要がある。比較対象の整数が同値である場合に最悪の処理時間となる。このコストは巨大な整数型や長い文字列など要素のエンコーディング長が大きい場合に無視できないものとなる。また、実数のデジタル表現として最も一般的な形式である浮動小数点の比較は、整数や短い文字列の比較よりも処理コストが高くなることが多い。
多くのコンピュータアーキテクチャでは、プロセッサはRAMとは別にハードウェアキャッシュを備えている。キャッシュはプロセッサ自体に内蔵されているためRAMよりはるかに高速だが、記憶容量は一般に少ない。そのため、プロセッサは最近アクセスされたメモリ位置とその近傍のデータをキャッシュに保持するのが一般的である。たとえば、配列の要素が読み出されるときは、その要素とRAM中で物理的に近いメモリ位置にある要素も同時にキャッシュに格納される。インデックスが近い要素に順次アクセスする処理はこれにより高速化されうる（参照の局所性）。しかし、整列配列に対する二分探索は、線形探索やハッシュテーブルにおけるのような順次アクセスを行うアルゴリズムとは異なり、配列が大きいと遠く離れたメモリ位置へジャンプすることがある。このため、多くのシステムでは大規模な配列に対する二分探索の実行時間がわずかに増加する。
二分探索とほかの方式の比較 整列配列に対する二分探索は、探索と同時に挿入や削除の操作を行う場合には非常に非効率であり、それらの操作ごとに の時間を必要とする。また整列配列はメモリ管理を複雑にする可能性があり、特に要素の挿入が頻繁に行われる状況ではそれが問題になる。整列配列よりも挿入や削除を効率的に行えるデータ構造も存在する。また、二分探索は完全一致の検索や集合への所属判定（検索対象の値がコレクションに含まれているかの確認）にも使えるが、それらの処理についてもより高速に実行可能なデータ構造が存在する。しかし、多くの探索方式と比べて二分探索は近似一致の処理の効率が良く、値の構造や型に関係なく 時間で実行できることが多い。加えて、最小値や最大値の取得など整列配列において効率よく実行できる操作もある。
線形探索 線形探索とは目標値を見つけるまですべてのレコードを順に調べていく単純な探索アルゴリズムであり、配列より挿入や削除が高速な連結リストに対しても行うことができる。整列配列に対する二分探索は配列が短い場合を除いて線形探索より高速だが、事前に配列をソートする必要がある。クイックソートやマージソートなど、要素間の比較に基づくすべてのソートアルゴリズムは、最悪ケースで最低 回の比較が必要になる。一方で、二分探索は線形探索と比べて近似一致探索を効率的に行うことができる。さらに、整列配列では最小値や最大値を高速に取得することができるが、未整列の配列では難しい。
木構造 右|サムネイル|二分探索木は二分探索と類似したアルゴリズムで検索される。 二分探索木は二分探索の原理に基づいて機能する二分木のデータ構造である。すべてのレコードが整列しており、各レコードの探索は二分探索に似たアルゴリズムによって平均して対数時間で行うことができる。二分探索木では挿入や削除の処理も平均で対数時間となり、整列配列における線形時間の挿入・削除より高速となりうる。また二分木は範囲検索や近似検索など整列配列で可能なすべての操作が実行可能である。
しかしながら、実際の二分探索木は完全に平衡ではない可能性が高く、そのため検索効率では整列配列の二分探索に劣るのが普通である。ノードの自動的な再配置によって自己平衡を行う平衡二分探索木においても、理想的な最小階層数の構造が得られることはまれである。平衡でない二分探索木では、内部ノードの多くが子ノードを1つしか持たず探索時間が平均・最悪ともに に近づくおそれがある。また、二分探索木は整列配列よりメモリ空間の消費が大きい。
その一方、二分探索木はファイルシステムの構造に効率的に組み込めるため、ハードディスクに格納された外部メモリの高速検索に適している。このような構造化を一般化したB木はデータベースやファイルシステムなどの長期記憶領域に広く用いられている。
ハッシュ法 連想配列を実装するにあたっては、ハッシュ関数を用いてキーをレコードに対応付けるハッシュテーブル構造の方が、整列されたレコード配列に対する二分探索よりも一般に高速である。ほとんどのハッシュテーブルの実装ではならし定数時間で処理が可能である。しかしながらハッシュ法は近似一致には適さない。たとえば、検索対象の次に小さい／次に大きい／最も近いキーを求めたいとしても、ハッシュ法による検索が失敗したときに得られる情報はレコード中に対象のキーが存在しないことだけである。二分探索はこうした近似一致の操作に構造的にも適しており、対数時間で実行できる。さらに、最小値や最大値の取得のような操作は整列配列では効率的に実行できるが、ハッシュテーブルでは困難である。
集合所属判定アルゴリズム 探索に関連した問題に集合への所属判定がある。二分探索のような検索アルゴリズムはいずれも集合所属判定に利用できる。ただし集合所属判定に特化した手法も存在する。ビット配列はそのうち最も単純な構造であり、キーの取り得る範囲が限られている場合に有効である。ビット配列は取りうるキーそれぞれにビットを1つずつ割り当てることで集合をコンパクトに保持する。所属判定は非常に高速で、 時間で実行可能である。（Judy1型）は64ビットキーを高効率で扱うことができる。
近似的な結果を許容する場合にはブルームフィルタが有力である。ブルームフィルタはハッシュ法に基づく確率的データ構造で、ビット配列と複数のハッシュ関数を用いてキーを符号化することで集合を格納する。ブルームフィルタはほとんどの場合ビット配列より空間効率がはるかに高く、速度ではそれほど見劣りしない。ハッシュ関数を 個使用する場合、所属判定の計算量は に抑えられる。ただしブルームフィルタの所属判定には偽陽性の問題がある。
その他のデータ構造 探索のみならず整列配列で可能な各種操作において二分探索よりも効率で上回りうるデータ構造も存在する。たとえば、探索や近似一致、そのほか整列配列に基づく各種の操作は、van Emde Boas木、、トライ木、ビット配列などの特殊なデータ構造を用いることで二分探索よりも効率よく実行できることがある。ただし、これらの特殊な構造が高速であるのは特定の性質を持つキーに最適化されているためであり（典型的にはキーが小さな整数である場合）、そのような性質を持たないキーに対しては時間や空間のコストがかさむことがある。キーに順序性がある限り、整列配列を用いれば、キーの性質にかかわらずある程度効率的にこれらの操作は実行可能である。Judy配列のような構造は、複数の手法を組み合わせることでキー特性への依存性を緩和しながら高効率と近似一致の機能を両立させている。
バリエーション
ユニフォーム二分探索 サムネイル|ユニフォーム二分探索では、上限・下限のインデックスではなく、現在の中点と2つの次の中点候補との間のインデックス差を記憶する。 ユニフォーム二分探索 (uniform binary search) では、配列インデックス範囲の上限と下限を記憶するのでなく、現在の中央要素と次の反復における中央要素のインデックス差を記憶する。具体的には、各回の反復におけるインデックス差を格納したルックアップテーブルをあらかじめ計算しておく。たとえば、0から10までのインデックスを持つ11要素の配列を探索する場合、最初の中央要素のインデックス は5である。このとき左側の部分配列のインデックスは0から4であり、中央要素は2となる。右側の部分配列の中央要素は8である。どちらのインデックスも から等しく3ずつ離れているため、この差分3があらかじめ格納される。インデックス範囲の上限と下限の平均を都度計算するのではなく、現在の中央要素インデックスに差分を加算もしくは減算することで次の中央要素インデックスを作るのである。のように平均を計算する効率が低いシステムは、ユニフォーム二分探索によって速度が改善される可能性がある。
指数探索 サムネイル|400ピクセル|指数探索の概念図。長い配列から探索対象値を含む範囲の部分配列を抜き出し、それに対して二分探索を実行する。 は二分探索を無限長のリストに拡張したものである。このアルゴリズムはまず「インデックスが2のべき乗であり、かつ探索対象の値より大きい最初の要素」を見つけることから始め、そのインデックスを上限に設定した上で二分探索に切り替える。探索対象の位置を として、前半の処理で 回、後半の二分探索部分で最大 回の比較が行われる。指数探索は有限長のリストでも機能するが、配列の先頭付近に探索対象がある場合に限って二分探索よりも高速になる。
内挿探索 サムネイル|400ピクセル|線形補間による内挿探索の概念図。このケースでは、配列内の目標値の位置が正確に推定されため探索が不要となっている。実装によっては目標値の位置を推定するために別の関数が用いられる。 では、中間点を計算するのではなく、要素の最小値と最大値、ならびに配列の長さを考慮して目標値の位置を推定する。その前提には、中間点は多くの場合で最良の推定位置ではないという点がある。たとえば、目標値が要素の最大値に近い場合、その値は配列の末尾近くに位置している可能性が高い。
一般的には内挿関数として線形補間が用いられる。配列を 、インデックスの上限と下限を と 、探索目標値を とすると、目標値は から までの範囲のうち 程度の位置にあると推定される。配列内の要素が一様またはほぼ一様に分布している場合、線形補間を用いた内挿探索では比較回数は 回となる。
実用上は、内挿探索は追加の計算を必要とするため小さな配列に対しては二分探索より遅くなる。内挿探索の時間計算量は二分探索よりも緩やかに増加するが、大きな配列にならなければ追加の計算のコストを相殺できない。
フラクショナル・カスケーディング サムネイル|400ピクセル|フラクショナル・カスケーディングでは、カスケードされた配列のそれぞれに、前段の配列から1つおきで抽出した要素へのポインタが織り込まれる。これにより、最後の配列に対して二分探索を行うだけで全ての配列を探索するのに近い結果が得られる。 は、複数の整列配列に対して同じ要素を探索する際に、二分探索によって高速な探索を行う手法である。配列を個別に探索する場合、 を配列数として所要時間は となる。フラクショナル・カスケーディングは配列中に他の配列の要素とその位置に関する情報を繰り込むことによって探索時間を に圧縮する。
フラクショナル・カスケーディングは計算幾何学の各種の問題を効率的に解くために開発された手法で、データマイニングやインターネット・プロトコルのルーティングのような分野にも応用されている。
グラフへの一般化 二分探索はある種のグラフにも適用できるよう一般化できる。この場合、値が格納されるのは配列要素ではなくグラフ頂点である。二分探索木はその一例であり、木構造の頂点（ノード）を照会することで、その頂点が目標と等しいかどうか、そうでなければどちらの部分木に目標が含まれるかを判定するアルゴリズムになる。さらにこれを一般化したアルゴリズムでは、正の重みを持つ重み付き無向グラフと探索目標が与えられたとき、ある頂点を照会すると、その頂点が目標であるかどうかを判定し、そうでない場合にはその頂点に接続する辺のうち目標頂点への最短経路上にあるものを選ぶ。いかなる正の重みを持つ重み付き無向グラフに対しても、最悪の場合でも 回の照会で目標の頂点を見つけ出すようなアルゴリズムが存在する。
ノイズのある二分探索