二分探索

探索 > 二分探索

二分探索

クラス	探索アルゴリズム
データ構造	配列
最悪計算時間	$O\left(\log n\right)$
最良計算時間	$O\left(1\right)$
平均計算時間	$O\left(\log n\right)$
最悪空間計算量	$O\left(1\right)$

二分探索アルゴリズムの視覚化。探索目標値は7である。

二分探索（英: binary search）もしくはバイナリサーチとは、計算機科学において整列配列の中から目標の値の位置を見つけ出す探索アルゴリズム。このアルゴリズムでは、探索目標と、配列の中央に位置する要素とをまず比較する。値が等しくない場合、目標が存在する可能性がない側の半分の部分配列を除外し、残りの半分について中央要素との比較を再び行う。この手続きを目標値が見つかるまで繰り返す。配列が空になって終了したなら、元の配列に目標値が存在しなかったということである。

二分探索は対数時間で動作するアルゴリズムであり、最悪のケースにおいて比較演算を $O(\log n)$ 回行う（ n は配列の要素数）。二分探索は配列が特に小さくなければ線形探索より高速であるが、実行するには配列があらかじめソートされていなければならない。ハッシュテーブルのように探索速度に特化したデータ構造ならば二分探索よりも効率よく探索を行うことができるが、二分探索は配列に目標の値が含まれない場合に最近傍の値を見つけるような応用がある。

二分探索には多くの変種がある。そのうちフラクショナル・カスケーディングは、複数の配列に対して同じ値の二分探索を行う高速な手法であり、計算幾何学など多くの分野における探索問題を効率的に解くことができる。指数探索は二分探索を無限長のリストに拡張したものである。二分探索木やB木といったデータ構造は二分探索に基づいている。

アルゴリズム

二分探索は整列配列に対して用いられる。まず配列の中央の要素と探索対象の値を比較し、一致している場合はその位置を返す。探索対象が中央要素より小さかったなら、配列の前半部に対して同じ手続きを行う。探索対象が中央の要素より大きかったなら後半部で探索をする。このように、各回の反復において、配列を二つに分けて探索対象が存在しないとわかった側の領域を除外していく。

手続き

長さ $n$ の配列 $A$ があり、要素の値もしくはレコード $A_{0},A_{1},A_{2},\ldots ,A_{n-1}$ は $A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}$ のようにソートされているとする。また探索目標値を $T$ とする。以下のサブルーチンは二分探索によって $A$ 内の要素 $T$ のインデックスを求める。

1. 変数 $L$ に $0$ を、$R$ に $n-1$ を代入する。
2. $L>R$ ならば探索は失敗して終了する。
3. 配列 $A$ の中央要素の位置を表す変数 $m$ に $L+\mathrm {floor} {\biggl (}{\frac {R-L}{2}}{\biggl )}$ を代入する。床関数 $\mathrm {floor}$ は引数 ${\frac {R-L}{2}}$ 以下の最大の整数を与える。
4. $A_{m}<T$ ならば $L$ に $m+1$ を代入し、ステップ2に戻る。
5. $A_{m}>T$ ならば $R$ に $m-1$ を代入し、ステップ2に戻る。
6. $A_{m}=T$ となったら探索は完了する。$m$ の値を返す。

この反復手続きは探索範囲を変数 $L$ および $R$ によって管理している。擬似コードで表すと以下のようになる。変数名と型は上記と同じであり、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

${\frac {R-L}{2}}$ に対して床関数ではなく天井関数を用いるアルゴリズムもある。その場合、探索目標の値が配列内に複数存在するとき結果が変わる可能性がある。

代替手法

上記の手続きでは、中央の要素 ($A_{m}$) が目標値 ($T$) と等しいかの判定を毎回の反復ごとに行っている。一部の実装では、この比較を反復の中では行わず、要素が1つだけ残ったとき（$L=R$になったとき）にのみ実行する。これにより、反復中の比較処理が1回減るためループが高速化されるが、反復回数は平均で1回増えるだけで済む。以降ではこの方法を「代替手法」と呼ぶ。

ヘルマン・ボッテンブルッフは1962年に等価判定を省略する実装を最初に公開した。

1. $L$ に $0$ を、$R$ に $n-1$ を代入する。
2. $L\neq R$ である間、以下を繰り返す。
   1. 中央要素の位置 $m$ に $L+\mathrm {ceiling} {\biggl (}{\frac {R-L}{2}}{\biggl )}$ を代入する。天井関数 $\mathrm {ceiling}$ は ${\frac {R-L}{2}}$ 以上の最小の整数を与える。
   2. $A_{m}>T$ であるならば、$R$ に $m-1$ を代入する。
   3. そうでないならば $A_{m}\leq T$ である。$L$ に $m$ を代入する。
3. $L=R$ となった時点で探索完了。$A_{L}=T$ ならば $L$ を返す。そうでなければ、目標値が見つからずに終了したことになる。

このバージョンの疑似コードは以下のようになる。

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

重複要素

配列内に重複する要素が存在する場合、この手続きは任意の目標値と等しい要素のインデックスを返す。たとえば、探索対象の配列が $[1,2,3,4,4,5,6,7]$、目標値が $4$ であれば、第4要素（インデックス3）と第5要素（インデックス4）のいずれを返してもアルゴリズムは正しく機能している。床関数を用いる手続きであれば第4要素を返す。重複要素の左端が常に返ってくるわけではなく、$[1,2,4,4,4,5,6,7]$ のような配列でも第4要素が返される。場合によっては、配列内で目標値が重複しているときその中の左端もしくは右端の要素を見つける必要がある。$[1,2,3,4,4,5,6,7]$ の例では、目標値 $4$ を持つ要素のうち第4要素が左端、第5要素が右端である。等価比較を省略する代替手法は、配列中に目標値が存在するならば常に右端の要素を返す。

左端の要素を探索する手続き

以下の手続きによれば目標値と等しい要素の左端を見つけることができる。

1. $L$ に $0$ を、$R$ に $n$ を代入する。
2. $L<R$ である間、以下を繰り返す。
   1. 中央要素の位置 $m$ を $L+\mathrm {floor} {\biggl (}{\frac {R-L}{2}}{\biggl )}$ とする。
   2. $A_{m}<T$ ならば $L$ に $m+1$ を代入する。
   3. そうでないならば $A_{m}\geq T$ である。$R$ に $m$ を代入する。
3. $L$ を返す。

$L<n$ かつ $A_{L}=T$ であれば、$A_{L}$ が $T$ に等しい要素の左端である。$T$ が配列に含まれなかったとしても、$L$ は配列 $A$ における $T$ の順位（ $T$ より小さい要素の数）を表している。

このバージョンの疑似コードは以下になる。

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

右端の要素を探索する手続き

以下の手続きで右端の要素を見つけることができる。

1. $L$ に $0$ を、$R$ に $n$ を代入する。
2. $L<R$ である間、以下を繰り返す。
   1. 中央要素の位置 $m$ に $L+\mathrm {floor} {\biggl (}{\frac {R-L}{2}}{\biggl )}$ を代入する。
   2. $A_{m}>T$ ならば $R$ に $m$ を代入する。
   3. そうでないならば $A_{m}\leq T$ である。$L$ に $m+1$ を代入する。
3. $R-1$ を返す。

$R>0$ かつ $A_{R-1}=T$ であれば、$A_{R-1}$ が $T$ に等しい要素の右端である。$T$ が配列に含まれなかったとしても、$n-R$ は配列 $A$ のうち $T$ より大きい要素の数を表している。

疑似コードは以下の通りである。

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

近似一致

二分探索は近似一致の計算にも応用できる。探索対象値の5が配列中に存在しない場合にも二分探索によって順位 (Rank)、直前要素 (Predecessor)、直後要素 (Successor)、最近接要素 (Nearest neighbor) が取得できる。

上記の手続きは完全一致の判定のみを行って目標値の位置を見つけるものである。しかし、二分探索は整列配列を対象としているため、近似一致の判定を行うように拡張することは容易である。たとえば、与えられた値に対して、順位（より小さい要素の数）、直前要素（次に値が小さい要素）、直後要素（次に値が大きい要素）、最も近い要素を求めるなどである。2つの値について順位を求めることで、それらの間にある要素数を求める範囲クエリも実行可能である。

• 順位クエリは左端要素を求める手続きによって実行できる。
• 直前要素クエリは順位クエリによって実行できる。目標値の順位が $r$ なら、直前要素のインデックスは $r-1$ である。
• 直後要素クエリは右端要素を求める手続きによって実行できる。返ってきたインデックスが $r$ なら、直後要素は $r+1$ である。
• 目標値の最近傍要素は、直前要素と直後要素のうち目標値に近い方である。
• 範囲クエリも容易に行うことができる。2つの値の順位を求めて差をとれば、大きい方の値未満で小さい方の値以上の要素数になる。端点を範囲に含めるかどうか、また配列に端点に等しい要素が存在するかどうかによって求めた数を1ずつ増減して調整する。

性能

二分探索を表す木構造。ここで探索対象となっている配列は $[20,30,40,50,80,90,100]$、探索目標値は $40$ である。

二分探索の最悪ケースでは、木構造の探索が最も深いレベルに到達する。最良ケースとなるのは目標値が配列の中央要素と一致したときである。

二分探索の性能のうち比較回数に関する部分は、手続きを二分探索木で表すことで評価できる。二分探索木の根ノードは配列の中央要素である。その子ノードは、左側が配列の前半の中央要素、右側が後半の中央要素となる。それ以降も同様に構築される。探索は根ノードから開始され、現在のノードの値を目標値と比較して大小に応じて左右の部分木をたどっていく。

最悪の場合、二分探索は比較ループを ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ 回反復する。${\textstyle \lfloor \cdot \rfloor }$ は引数以下の最大の整数を返す床関数、${\textstyle \log _{2}}$ は二進対数である。二分探索木の階層数は常に ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ になり、その最深層に到達するのが最悪ケースにあたる。

目標の要素が配列内に存在しないならば、場合によって最悪ケースとなる。${\textstyle n}$ が2のべき乗から1を引いた値であれば常にこれが当てはまる。それ以外の配列長では、反復数 ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ 回で探索木の最深層に到達することもあり、反復数 ${\textstyle \lfloor \log _{2}(n)\rfloor }$ 回（最深層より一つ上）で探索が終了することもある。

全要素が等しい確率で探索対象となるとして反復回数を平均すると、目標要素が配列内に存在する場合には $\lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n$ 回となる。これは $\log _{2}(n)-1$ 回におよそ等しい。目標要素が配列内に存在しない場合、目標要素の挿入位置が両端も含めた要素間の中から等確率で選ばれるならば、反復回数は$\lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)$回となる。

最良ケースとなるのは目標値が配列の中央要素と一致している場合で、反復1回のみでその位置が返される。

反復回数の点では、要素同士の比較のみに基づく探索アルゴリズムのうち、平均および最悪ケースにおいて二分探索より優れた性能を示すものは存在しない。二分探索を表す比較木は最下層を除くすべての階層が完全に埋まっているため、階層数は限界まで最小化されている。木構造がそれ以外のものになると、1回の反復で除外できる要素数が減ることになるため、平均および最悪ケースでの反復回数が増える。このため、二分探索以外の比較ベースのアルゴリズムは、特定の目標値に対しては二分探索より速い場合があるとしても、すべての要素にわたって平均した性能では劣る。二分探索は配列を二分割することで部分配列のサイズを可能な限り均等に保っている。

空間計算量

二分探索では、配列の大きさにかかわらず、要素を指定するためのポインタ（配列インデックス、もしくはメモリ位置へのポインタ）を3つ必要とする。すなわち、Word RAMモデルにおいて二分探索の空間計算量は $O(1)$ である。

平均ケースの導出

二分探索における平均の反復回数は、探索対象がどのような確率で選ばれるかに依存する。また探索が成功する場合と失敗する場合でも異なる。ここでは、成功する場合については、すべての配列要素が等確率で探索対象になると仮定する。失敗する場合では、すべての要素間および両端の外の各区間が等確率で選ばれるとする。成功時の平均ケースは、すべての要素を一度ずつ探索したときに必要な反復回数の合計を要素数 $n$ で割ったものである。失敗時の平均ケースは、各区間で一度ずつ探索を行ったときの反復回数の合計を区間数 $n+1$ で割ったものである。

探索対象が見つかる場合

二分木表現において、探索対象が見つかる場合の探索は根から目標ノードまでのパスとして表される。これを内部パス (internal path) と呼ぶ。パスの長さは含まれるエッジ（ノード間の接続）の数で与えられる。パス長を $l$ とすれば、その探索の反復回数は初回の比較を含めて $l+1$ 回となる。すべての内部パスの長さの合計を内部パス長 (internal path length) とする。各ノードには根からのパスが一意に存在するため、一つの内部パスが一つの要素を対象とする探索を表すことになる。要素の数が正整数 n であり、かつ内部パス長が $I(n)$ なら、探索が成功する場合の反復回数の平均は $T(n)=1+{\frac {I(n)}{n}}$ で与えられる。加算されている1はすべての探索で必要になる初回の比較を表す。

二分探索は比較に基づく探索アルゴリズムとして最適であるため、探索成功時の平均反復回数は、ノード数 n のあらゆる二分木のうち最小の内部パス長を求める問題に帰着する。その値は以下で与えられる。

$$I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor$$

たとえば要素数7の配列では、根ノードが表す探索は反復回数が1回のみであり、根の下に位置する2要素はそれぞれ2回、その下の4要素はそれぞれ3回の反復を必要とする。この場合の内部経路長は以下である。

$$\sum _{k=1}^{7}\left\lfloor \log _{2}(k)\right\rfloor =0+2\times 1+4\times 2=2+8=10$$

平均の反復回数は $T(n)=1+{\frac {10}{7}}=2{\frac {3}{7}}$ となる。

$I(n)$ の総和は以下のようにも書き換えられる。

$$I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor =(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2$$

この $I(n)$ を $T(n)$ の式に代入すると以下が得られる。

$$T(n)=1+{\frac {(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2}{n}}=\lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n$$

n が整数であれば、上式は、成功する探索について先に述べた平均ケースの式と等価である。

探索対象が見つからない場合

配列中に目標値が見つからないような探索は、木構造に外部ノード (external nodes) を追加することで表現できる。そのようにして得られる木を拡張二分木 (extended binary tree) と呼ぶ。内部ノード（木に元々含まれていたノード）すべてについて、子ノードを2つ未満しか持たないならば外部ノードを子として追加することで子を必ず2つ持つようにする。これにより、失敗する探索は一つの外部ノードへのパスとして表される。その外部ノードの親は、探索中の最後の反復で残った配列要素に対応する。根から外部ノードに至る経路を外部パス (external path)、すべての外部パスの長さの総和を外部パス長 (external path length) と呼ぶ。要素数が正整数 $n$、外部パス長が $E(n)$ であれば、目標値が見つからない探索における平均反復回数は、最初の反復を含めて $T'(n)={\frac {E(n)}{n+1}}$ となる。外部パス長が $n$ ではなく $n+1$ で割られているのは、配列の各要素の間、および両端に存在する区間に対応して $n+1$ 個の外部経路が存在するためである。

目標値が見つかる探索の場合と同様に、この問題もノード数 n のあらゆる二分木のうち最小の外部パス長を求める問題に帰着する。いかなる二分木も外部パス長は内部パス長より $2n$ だけ多いので、$I(n)$ の式を代入して

$$E(n)=I(n)+2n=\left[(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2\right]+2n=(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}$$

となる。この $E(n)$ を $T'(n)$ に代入することで、探索が失敗する場合の平均ケースを求められる。

$$T'(n)={\frac {(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}}{(n+1)}}=\lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)$$

代替手法の性能

本項の初めに定義した二分探索の手続きでは、毎回の反復で中央要素が探索目標と等しいかをチェックする。比較回数は反復ごとに1回もしくは2回であり、すべての要素が等しい確率で探索されるならば平均して反復ごとに1.5回となる。それに対し、すべての反復が終わった後に残った要素に対して1回だけ探索目標と等しいかのチェックを行う代替手法では、反復ごとに平均で0.5回の比較が省略できる。そのかわりに必ず最大の回数の反復が行われるため、反復回数は1つの探索につき平均1回増加してしまう。比較ループは最悪ケースでも ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ 回しか行われないため、反復ごとの効率がわずかに上昇するとしても、${\textstyle n}$ が非常に大きい場合を除けば余分な1回の反復を埋め合わせるには十分ではない。

実行時間とキャッシュ使用

二分探索の性能評価では要素の比較に要する時間も考慮の対象となる。整数や文字列の比較時間は通常そのエンコーディング長（多くの場合ビット数）に比例して増加する。たとえば、64ビット符号なし整数同士の比較であれば、32ビットの場合と比べて最大で2倍のビット数を比較する必要がある。比較対象の整数が同値である場合に最悪の処理時間となる。このコストは巨大な整数型や長い文字列など要素のエンコーディング長が大きい場合に無視できないものとなる。また、実数のデジタル表現として最も一般的な形式である浮動小数点の比較は、整数や短い文字列の比較よりも処理コストが高くなることが多い。

多くのコンピュータアーキテクチャでは、プロセッサはRAMとは別にハードウェアキャッシュを備えている。キャッシュはプロセッサ自体に内蔵されているためRAMよりはるかに高速だが、記憶容量は一般に少ない。そのため、プロセッサは最近アクセスされたメモリ位置とその近傍のデータをキャッシュに保持するのが一般的である。たとえば、配列の要素が読み出されるときは、その要素とRAM中で物理的に近いメモリ位置にある要素も同時にキャッシュに格納される。インデックスが近い要素に順次アクセスする処理はこれにより高速化されうる（参照の局所性）。しかし、整列配列に対する二分探索は、線形探索やハッシュテーブルにおける線形探査のような順次アクセスを行うアルゴリズムとは異なり、配列が大きいと遠く離れたメモリ位置へジャンプすることがある。このため、多くのシステムでは大規模な配列に対する二分探索の実行時間がわずかに増加する。

二分探索とほかの方式の比較

整列配列に対する二分探索は、探索と同時に挿入や削除の操作を行う場合には非常に非効率であり、それらの操作ごとに ${\textstyle O(n)}$ の時間を必要とする。また整列配列はメモリ管理を複雑にする可能性があり、特に要素の挿入が頻繁に行われる状況ではそれが問題になる。整列配列よりも挿入や削除を効率的に行えるデータ構造も存在する。また、二分探索は完全一致の検索や集合への所属判定（検索対象の値がコレクションに含まれているかの確認）にも使えるが、それらの処理についてもより高速に実行可能なデータ構造が存在する。しかし、多くの探索方式と比べて二分探索は近似一致の処理の効率が良く、値の構造や型に関係なく ${\textstyle O(\log n)}$ 時間で実行できることが多い。加えて、最小値や最大値の取得など整列配列において効率よく実行できる操作もある。

線形探索

線形探索とは目標値を見つけるまですべてのレコードを順に調べていく単純な探索アルゴリズムであり、配列より挿入や削除が高速な連結リストに対しても行うことができる。整列配列に対する二分探索は配列が短い場合を除いて線形探索より高速だが、事前に配列をソートする必要がある。クイックソートやマージソートなど、要素間の比較に基づくすべてのソートアルゴリズムは、最悪ケースで最低 ${\textstyle O(n\log n)}$ 回の比較が必要になる。一方で、二分探索は線形探索と比べて近似一致探索を効率的に行うことができる。さらに、整列配列では最小値や最大値を高速に取得することができるが、未整列の配列では難しい。

木構造

二分探索木は二分探索と類似したアルゴリズムで検索される。

二分探索木は二分探索の原理に基づいて機能する二分木のデータ構造である。すべてのレコードが整列しており、各レコードの探索は二分探索に似たアルゴリズムによって平均して対数時間で行うことができる。二分探索木では挿入や削除の処理も平均で対数時間となり、整列配列における線形時間の挿入・削除より高速となりうる。また二分木は範囲検索や近似検索など整列配列で可能なすべての操作が実行可能である。

しかしながら、実際の二分探索木は完全に平衡ではない可能性が高く、そのため検索効率では整列配列の二分探索に劣るのが普通である。ノードの自動的な再配置によって自己平衡を行う平衡二分探索木においても、理想的な最小階層数の構造が得られることはまれである。平衡でない二分探索木では、内部ノードの多くが子ノードを1つしか持たず探索時間が平均・最悪ともに ${\textstyle n}$ に近づくおそれがある。また、二分探索木は整列配列よりメモリ空間の消費が大きい。

その一方、二分探索木はファイルシステムの構造に効率的に組み込めるため、ハードディスクに格納された外部メモリの高速検索に適している。このような構造化を一般化したB木はデータベースやファイルシステムなどの長期記憶領域に広く用いられている。

ハッシュ法

連想配列を実装するにあたっては、ハッシュ関数を用いてキーをレコードに対応付けるハッシュテーブル構造の方が、整列されたレコード配列に対する二分探索よりも一般に高速である。ほとんどのハッシュテーブルの実装ではならし定数時間で処理が可能である。しかしながらハッシュ法は近似一致には適さない。たとえば、検索対象の次に小さい／次に大きい／最も近いキーを求めたいとしても、ハッシュ法による検索が失敗したときに得られる情報はレコード中に対象のキーが存在しないことだけである。二分探索はこうした近似一致の操作に構造的にも適しており、対数時間で実行できる。さらに、最小値や最大値の取得のような操作は整列配列では効率的に実行できるが、ハッシュテーブルでは困難である。

集合所属判定アルゴリズム

探索に関連した問題に集合への所属判定がある。二分探索のような検索アルゴリズムはいずれも集合所属判定に利用できる。ただし集合所属判定に特化した手法も存在する。ビット配列はそのうち最も単純な構造であり、キーの取り得る範囲が限られている場合に有効である。ビット配列は取りうるキーそれぞれにビットを1つずつ割り当てることで集合をコンパクトに保持する。所属判定は非常に高速で、${\textstyle O(1)}$ 時間で実行可能である。ジュディ配列（Judy1型）は64ビットキーを高効率で扱うことができる。

近似的な結果を許容する場合にはブルームフィルタが有力である。ブルームフィルタはハッシュ法に基づく確率的データ構造で、ビット配列と複数のハッシュ関数を用いてキーを符号化することで集合を格納する。ブルームフィルタはほとんどの場合ビット配列より空間効率がはるかに高く、速度ではそれほど見劣りしない。ハッシュ関数を ${\textstyle k}$ 個使用する場合、所属判定の計算量は ${\textstyle O(k)}$ に抑えられる。ただしブルームフィルタの所属判定には偽陽性の問題がある。

その他のデータ構造

探索のみならず整列配列で可能な各種操作において二分探索よりも効率で上回りうるデータ構造も存在する。たとえば、探索や近似一致、そのほか整列配列に基づく各種の操作は、van Emde Boas木、フュージョン木、トライ木、ビット配列などの特殊なデータ構造を用いることで二分探索よりも効率よく実行できることがある。ただし、これらの特殊な構造が高速であるのは特定の性質を持つキーに最適化されているためであり（典型的にはキーが小さな整数である場合）、そのような性質を持たないキーに対しては時間や空間のコストがかさむことがある。キーに順序性がある限り、整列配列を用いれば、キーの性質にかかわらずある程度効率的にこれらの操作は実行可能である。Judy配列のような構造は、複数の手法を組み合わせることでキー特性への依存性を緩和しながら高効率と近似一致の機能を両立させている。

バリエーション

ユニフォーム二分探索

ユニフォーム二分探索では、上限・下限のインデックスではなく、現在の中点と2つの次の中点候補との間のインデックス差を記憶する。

ユニフォーム二分探索 (uniform binary search) では、配列インデックス範囲の上限と下限を記憶するのでなく、現在の中央要素と次の反復における中央要素のインデックス差を記憶する。具体的には、各回の反復におけるインデックス差を格納したルックアップテーブルをあらかじめ計算しておく。たとえば、0から10までのインデックスを持つ11要素の配列を探索する場合、最初の中央要素のインデックス $m$ は5である。このとき左側の部分配列のインデックスは0から4であり、中央要素は2となる。右側の部分配列の中央要素は8である。どちらのインデックスも $m=5$ から等しく3ずつ離れているため、この差分3があらかじめ格納される。インデックス範囲の上限と下限の平均を都度計算するのではなく、現在の中央要素インデックスに差分を加算もしくは減算することで次の中央要素インデックスを作るのである。10進コンピュータのように平均を計算する効率が低いシステムは、ユニフォーム二分探索によって速度が改善される可能性がある。

指数探索

指数探索の概念図。長い配列から探索対象値を含む範囲の部分配列を抜き出し、それに対して二分探索を実行する。

指数探索は二分探索を無限長のリストに拡張したものである。このアルゴリズムはまず「インデックスが2のべき乗であり、かつ探索対象の値より大きい最初の要素」を見つけることから始め、そのインデックスを上限に設定した上で二分探索に切り替える。探索対象の位置を ${\textstyle x}$ として、前半の処理で ${\textstyle \lfloor \log _{2}x+1\rfloor }$ 回、後半の二分探索部分で最大 ${\textstyle \lfloor \log _{2}x\rfloor }$ 回の比較が行われる。指数探索は有限長のリストでも機能するが、配列の先頭付近に探索対象がある場合に限って二分探索よりも高速になる。

内挿探索

線形補間による内挿探索の概念図。このケースでは、配列内の目標値の位置が正確に推定されため探索が不要となっている。実装によっては目標値の位置を推定するために別の関数が用いられる。

内挿探索では、中間点を計算するのではなく、要素の最小値と最大値、ならびに配列の長さを考慮して目標値の位置を推定する。その前提には、中間点は多くの場合で最良の推定位置ではないという点がある。たとえば、目標値が要素の最大値に近い場合、その値は配列の末尾近くに位置している可能性が高い。

一般的には内挿関数として線形補間が用いられる。配列を $A$、インデックスの上限と下限を $L$ と $R$、探索目標値を $T$ とすると、目標値は $L$ から $R$ までの範囲のうち $(T-A_{L})/(A_{R}-A_{L})$ 程度の位置にあると推定される。配列内の要素が一様またはほぼ一様に分布している場合、線形補間を用いた内挿探索では比較回数は ${\textstyle O(\log \log n)}$ 回となる。

実用上は、内挿探索は追加の計算を必要とするため小さな配列に対しては二分探索より遅くなる。内挿探索の時間計算量は二分探索よりも緩やかに増加するが、大きな配列にならなければ追加の計算のコストを相殺できない。

フラクショナル・カスケーディング

フラクショナル・カスケーディングでは、カスケードされた配列のそれぞれに、前段の配列から1つおきで抽出した要素へのポインタが織り込まれる。これにより、最後の配列に対して二分探索を行うだけで全ての配列を探索するのに近い結果が得られる。

フラクショナル・カスケーディング は、複数の整列配列に対して同じ要素を探索する際に、二分探索によって高速な探索を行う手法である。配列を個別に探索する場合、${\textstyle k}$ を配列数として所要時間は ${\textstyle O(k\log n)}$ となる。フラクショナル・カスケーディングは配列中に他の配列の要素とその位置に関する情報を繰り込むことによって探索時間を ${\textstyle O(k+\log n)}$ に圧縮する。

フラクショナル・カスケーディングは計算幾何学の各種の問題を効率的に解くために開発された手法で、データマイニングやインターネット・プロトコルのルーティングのような分野にも応用されている。

グラフへの一般化

二分探索はある種のグラフにも適用できるよう一般化できる。この場合、値が格納されるのは配列要素ではなくグラフ頂点である。二分探索木はその一例であり、木構造の頂点（ノード）を照会することで、その頂点が目標と等しいかどうか、そうでなければどちらの部分木に目標が含まれるかを判定するアルゴリズムになる。さらにこれを一般化したアルゴリズムでは、正の重みを持つ重み付き無向グラフと探索目標が与えられたとき、ある頂点を照会すると、その頂点が目標であるかどうかを判定し、そうでない場合にはその頂点に接続する辺のうち目標頂点への最短経路上にあるものを選ぶ。いかなる正の重みを持つ重み付き無向グラフに対しても、最悪の場合でも $O(\log n)$ 回の照会で目標の頂点を見つけ出すようなアルゴリズムが存在する。

ノイズのある二分探索

ノイズのある二分探索では、比較処理が一定の確率で誤った結果を返す。

ノイズのある二分探索 (noisy binary search) は配列要素の比較に確実性がない問題に対するアルゴリズムであり、各回の比較結果が一定の確率で誤っているにもかかわらず所定の正確さで目標値の位置を見つけ出すことができる。この種の手法はいずれも、平均して少なくとも $(1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}$ 回の比較を必要とする。ここで $H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)$ は二値エントロピー関数、$p$ は各回の比較の正答率、$\tau$ は探索によって返される位置が誤っている確率である。ノイズのある二分探索の問題はレーニ＝ウラムのゲーム（20の質問の変種で回答が確率的に誤る) の一種とみなすことができる。

量子二分探索

古典コンピュータでは、二分探索の最悪ケースで正確に ${\textstyle \lfloor \log _{2}n+1\rfloor }$ 回の反復が必要となる。量子アルゴリズムによる二分探索でもクエリ回数（古典計算における反復回数にあたる）は ${\textstyle \log _{2}n}$ の定数倍が上限となるが、その係数は1より小さい。厳密な（常に正しい結果を返す）量子二分探索手続きは最悪ケースで少なくとも ${\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n}$ 回のクエリが必要となる。ここで ${\textstyle \ln }$ は自然対数を表す。また、最悪ケースで ${\textstyle 4\log _{605}n\approx 0.433\log _{2}n}$ 回で動作する厳密な量子二分探索の手法も存在する。なお、非整列リストからの要素探索ではグローバーのアルゴリズムが最適な量子アルゴリズムであり、必要なクエリ数は $O({\sqrt {n}})$ 回である。

歴史

検索を高速化するためリスト項目をソートする発想は古代にまで遡る。最古の例として知られているのは紀元前200年ごろのバビロニアで作られた Inakibit-Anu 粘土板である。この粘土板にはおよそ500個の60進数が探しやすいように辞書式順に並べられ、それぞれの逆数が記されていた。エーゲ海諸島でも頭文字で整列された名簿が複数発見されている。1286年に編纂されたラテン語辞典『カトリコン』は、頭文字付近だけでなく完全なアルファベット順で単語を整列する規則について記した最初の文献である。

1946年には、先駆的な計算機科学の大学講座「ムーア・スクール・レクチャーズ」においてジョン・モークリーが二分探索に初めて言及した。1957年、ウィリアム・ウェスレイ・ピーターソンが内挿探索の最初の手法を発表した。この時期に発表された二分探索アルゴリズムはいずれも配列の長さが2の累乗から1を引いた形でなければ機能しなかったが、1960年にデリック・ヘンリー・レーマーが任意の長さの配列で機能する二分探索アルゴリズムを発表した。1962年にはヘルマン・ボッテンブルッフが、検索対象との等値比較を反復の最後に移すことで、反復回数が平均で1回増加するかわりに反復あたりの比較回数を1回に減らす代替手法のアルゴリズムをALGOL 60への実装として発表した。1971年にはスタンフォード大学のA・K・チャンドラによってユニフォーム二分探索が開発された。1986年にはバーナード・チャゼルとレオニダス・J・ギバスが計算幾何学における各種の探索問題を解決する手法としてフラクショナル・カスケーディングを開発した。

実装上の問題

二分探索の基本的なアイディアは比較的分かりやすいが、細部は驚くほど厄介だ。

—ドナルド・クヌース

ジョン・ベントリーは、職業的なプログラマ向けの講座で二分探索を課題にしたところ、90％の受講者が数時間かけても正しい解法を得られなかったと伝えている。それらの受講者による実装はまれなエッジケースにおいて誤動作を起こしたり、誤った解答を返した。1988年の研究によると、二分探索の正確なコードを掲載していた教科書は20冊中5冊に過ぎなかった。ベントリー自身の1986年の著書 Programming Pearls（『珠玉のプログラミング』2000年、丸善出版）に掲載されていた二分探索の実装にもオーバーフローのバグが含まれており、20年以上にわたって見過ごされた。Java言語のライブラリに含まれていた二分探索の実装にも9年以上にわたって同様のオーバーフローのバグがあった。

実際の実装では、インデックスを表す変数が固定長（整数型）であることが多く、非常に大きな配列に対しては数値のオーバーフローが生じる可能性がある。区間の中点を ${\frac {L+R}{2}}$ として計算すると、$L$ および $R$ 自体はデータ型の範囲内であっても $L+R$ が範囲を超えてしまうことがある。$L$ と $R$ が非負である場合は $L+{\frac {R-L}{2}}$ として計算すればこの問題を避けられる。

そのほか、ループの終了条件が正しく定義されていないと無限ループが発生する可能性がある。$L$ が $R$ を超えることがあれば、その時点で探索は失敗であり、明示的に失敗の処理を行わなければならない。また目標の要素が見つかった場合にもループから抜ける必要がある。目標値との等値判定を毎回のループで行わない代替手法の実装では、探索が成功したか失敗したかの判定を適切な場所に置く必要がある。ベントリーによれば、二分探索を誤って実装したプログラマの多くは、この終了条件の定義に誤りを犯していた。

ライブラリによるサポート

多くのプログラム言語の標準ライブラリには二分探索のルーチンが含まれている。

• C言語では標準ライブラリに bsearch() 関数がある。この関数は二分探索で実装されるのが一般的だが、公式の標準でそのように規定されているわけではない。
• C++の標準ライブラリでは binary_search()、lower_bound()、upper_bound()、equal_range() のような関数が提供されている。
• D言語の標準ライブラリである Phobos の std.range モジュールには、sort() 関数および assumeSorted() 関数によって得られる SortedRange() 型がある。この型には contains()、equalRange()、lowerBound()、trisect() といったメソッドが用意されており、対象となるデータがランダムアクセス可能な場合には、これらのメソッドはデフォルトで二分探索として実行される。
• COBOLでは順序付き表に二分探索を行うための SEARCH ALL 命令が提供されている。
• Goの標準ライブラリに含まれる sort パッケージには、一般的な二分探索を行う関数として Search があるほか、整数・浮動小数点数・文字列のスライスを対象とする SearchInts、SearchFloat64s、SearchStrings が用意されている。
• Javaの標準的な java.util パッケージに含まれる Arrays クラスおよび Collections クラスでは、それぞれJava配列および List に対して二分探索を行うため、オーバーロードされた一連の静的メソッドである binarySearch() が用意されている。
• Microsoftの.NET Framework 2.0 では、代表的なコレクション型に対しては、ジェネリックプログラミングに基づいた二分探索アルゴリズムが主に静的メソッドとして提供されている。たとえば、System.Array クラスには、任意の型に対して適用可能な BinarySearch<T>(T[] array, T value) メソッドがある。
• Objective-Cでは、Cocoaフレームワークにおいて、NSArray クラスの indexOfObject:inSortedRange:options:usingComparator: メソッドが Mac OS X 10.6 以降で利用可能である。また Apple が提供するC言語フレームワークである Core Foundation にも CFArrayBSearchValues() 関数が用意されている。
• Pythonでは bisect モジュールが提供されており、リストに挿入を行うたびにソートを実行しなくても整列済みの状態を保つことができる。
• Rubyの Array クラスは近似一致が組み込まれた bsearch メソッドを持つ。
• Rustの slice プリミティブ型には binary_search()、binary_search_by()、binary_search_by_key()、partition_point() のメソッドがある。

関連項目

• 二分法 — 二分探索と同様の考え方により、実数の範囲で関数の零点を見つけるアルゴリズム。
• en:Multiplicative binary search — 中点の計算を簡略化した二分探索のバリエーション。

脚注

本記事の2025年5月22日 (木) 22:46版の翻訳元である英語版Wikipedia記事「Binary search」は2018年に WikiJournal of Science 誌に投稿され、外部の専門家によるピアレビューを受けた（レビュー結果）。修正を加えた版は2019年にCC-BY-SA-3.0ライセンスでWikipedia上で再度公開されている（修正履歴）。レビュー直後の版は以下の通り。

• Anthony Lin; et al. (2018-06-01). “Binary search”. WikiJournal of Science 2 (1): 5. doi:10.15347/WJS/2019.005. ISSN 2470-6345. Binary search algorithm (Q81434400). https://upload.wikimedia.org/wikiversity/en/e/ea/Binary_search_algorithm.pdf. 

参考文献

• Bentley, Jon (2000). Programming pearls (2nd ed.). Addison-Wesley. ISBN 978-0-201-65788-3 
• Butterfield, Andrew; Ngondi, Gerard E. (2016). A dictionary of computer science (7th ed.). Oxford, UK: Oxford University Press. ISBN 978-0-19-968897-5 
• Chang, Shi-Kuo (2003). Data structures and algorithms. Software Engineering and Knowledge Engineering. 13. Singapore: World Scientific. ISBN 978-981-238-348-8 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 978-0-262-03384-8 
• Fitzgerald, Michael (2015). Ruby pocket reference. Sebastopol, California: O'Reilly Media. ISBN 978-1-4919-2601-7 
• Goldman, Sally A.; Goldman, Kenneth J. (2008). A practical guide to data structures and algorithms using Java. Boca Raton, Florida: CRC Press. ISBN 978-1-58488-455-2 
• Kasahara, Masahiro; Morishita, Shinichi (2006). Large-scale genome sequence processing. London, UK: Imperial College Press. ISBN 978-1-86094-635-6 
• Knuth, Donald (1997). Fundamental algorithms. The Art of Computer Programming. 1 (3rd ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-89683-1 
• Knuth, Donald (1998). Sorting and searching. The Art of Computer Programming. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-89685-5 
• Knuth, Donald (2011). Combinatorial algorithms. The Art of Computer Programming. 4A (1st ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-03804-0 
• Moffat, Alistair; Turpin, Andrew (2002). Compression and coding algorithms. Hamburg, Germany: Kluwer Academic Publishers. doi:10.1007/978-1-4615-0935-6. ISBN 978-0-7923-7668-2 
• Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Upper Saddle River, New Jersey: Addison-Wesley Professional. ISBN 978-0-321-57351-3. http://algs4.cs.princeton.edu/home/  Condensed web version ; book version .
• Stroustrup, Bjarne (2013). The C++ programming language (4th ed.). Upper Saddle River, New Jersey: Addison-Wesley Professional. ISBN 978-0-321-56384-2 

外部リンク

• NIST Dictionary of Algorithms and Data Structures: binary search
• Comparisons and benchmarks of a variety of binary search implementations in C Archived 25 September 2019 at the Wayback Machine.