二分探索

コンピュータサイエンスにおいて、二分探索（ハーフインターバルサーチ^[1] 、対数探索^[2]、バイナリチョップ^{[3]とも呼ばれる）は、ソートされた配列[4]}内から目的の値の位置を見つける探索アルゴリズムである。^[5^]二分探索は、目的の値と配列の中央の要素を比較する。両者が等しくない場合、目的の値が存在しない半分は除外され、残りの半分で探索が続けられ、再び中央の要素と目的の値を比較し、目的の値が見つかるまでこれを繰り返す。残りの半分が空のまま探索が終了した場合、目的の値は配列内に存在しない。

二分探索は最悪の場合で対数時間で実行され、を比較します。ここでは配列の要素数です。 ^[a]^{[6]二分探索は小さな配列を除いて}線形探索よりも高速です。しかし、二分探索を適用するには、まず配列をソートする必要があります。ハッシュテーブルなど、二分探索よりも効率的に探索できる、高速探索用に設計された特殊なデータ構造があります。ただし、二分探索は、ターゲットを基準として配列内の次に小さい要素や次に大きい要素を（配列に存在しない場合でも）見つけるなど、より広範囲の問題を解決するために使用できます。 $O(\log n)$ $n$

二分探索には様々なバリエーションがあります。特に、分数カスケーディングは、複数の配列における同じ値の二分探索を高速化します。分数カスケーディングは、計算幾何学をはじめとする様々な分野における多くの探索問題を効率的に解決します。指数探索は、二分探索を無限リストに拡張します。二分探索木とB木データ構造は、二分探索に基づいています。

アルゴリズム

二分探索はソートされた配列に対して機能します。二分探索は、配列の中央にある要素と目的の値を比較することから始まります。目的の値が要素と一致する場合、配列内のその位置が返されます。目的の値が要素より小さい場合、探索は配列の下半分で続行されます。目的の値が要素より大きい場合、探索は配列の上半分で続行されます。これにより、アルゴリズムは各反復において、目的の値が存在できない半分を排除します。^[7]

手順

、目標値のようにソートされた値またはレコードを持つ要素の配列が与えられた場合、次のサブルーチンはバイナリサーチを使用して内ののインデックスを見つけます。^[7] $A$ $n$ $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$ $T$ $A$

を、をに設定します。 $L$ $0$ $R$ $n-1$
の場合、検索は失敗として終了します。 $L>R$
(中央の要素の位置)をの下限値( より小さいか等しい最大の整数)に加算した値に設定します。 $m$ $L$ ${\frac {RL}{2}}$ ${\frac {RL}{2}}$
の場合はに設定し、手順 2 に進みます。 $A_{m$ $L$ $m+1$
の場合はに設定し、手順 2 に進みます。 $A_{m}>T$ $R$ $m-1$
これで、検索は完了です。を返します。 $A_{m}=T$ $m$

この反復手順は、2つの変数とを用いて探索境界を追跡する。この手順は擬似コードで以下のように表現できる。変数名と型は上記と同じであり、は床関数であり、は探索の失敗を示す特定の値を参照する。^[7] $L$ $R$ floorunsuccessful

関数binary_search(A, n, T)は
    L := 0
    R := n − 1
    L ≤ Rの場合
        m := L + floor((R - L) / 2)
        A[m] < Tならば
            L := m + 1
        そうでなければ、A [m] > Tならば
            R := m − 1
        そうでない場合:
             m
    を返す失敗を
返す

あるいは、アルゴリズムはの上限を取ることもあります。この場合、対象値が配列内に複数回出現すると、結果が変わる可能性があります。 ${\frac {RL}{2}}$

代替手順

上記の手順では、アルゴリズムは各反復において、中間要素（）がターゲット要素（）と等しいかどうかを確認します。実装によっては、各反復におけるこの確認を省略するものもあります。アルゴリズムは、要素が1つ残っている場合（の場合）のみこの確認を実行します。これにより、反復ごとに1つの比較が削減されるため、比較ループが高速化され、平均して1回の反復処理で済みます。^[8] $m$ $T$ $L=R$

ヘルマン・ボッテンブルッフは1962年にこのチェックを省略した最初の実装を公開した。^[8]^[9]

を、をに設定します。 $L$ $0$ $R$ $n-1$
その間、 $L\neq R$
1. (中央の要素の位置)をの上限値( 以上の最小の整数)に加算して設定します。 $m$ $L$ ${\frac {RL}{2}}$ ${\frac {RL}{2}}$
2. の場合はに設定します。 $A_{m}>T$ $R$ $m-1$
3. それ以外の場合は、;に設定されます。 $A_{m}\leq T$ $L$ $m$
これで検索は完了です。の場合はを返します。それ以外の場合は、検索は失敗として終了します。 $L=R$ $A_{L}=T$ $L$

ceil天井関数はどこにありますか。このバージョンの疑似コードは次のとおりです。

関数binary_search_alternative(A, n, T)は
    L := 0
    R := n − 1
    L != Rの場合
        m := L + ceil((R - L) / 2)
        A[m] > Tならば
            R := m − 1
        それ以外：
            L := m
    A[L] = Tの場合、
         L
    を返す。失敗を
返す。

重複要素

この手順は、配列内に重複する要素があっても、要素がターゲット値と等しい任意のインデックスを返すことがあります。たとえば、検索対象の配列がで、ターゲットがの場合、アルゴリズムが 4 番目 (インデックス 3) または 5 番目 (インデックス 4) の要素を返すのは正しいことになります。通常の手順では、この場合 4 番目の要素 (インデックス 3) を返します。常に最初の重複が返されるわけではありません (それでも 4 番目の要素を返す場合を考えてみましょう)。ただし、配列内で重複しているターゲット値の左端または右端の要素を見つける必要がある場合があります。上記の例では、4 番目の要素は値 4 の左端の要素であり、5 番目の要素は値 4 の右端の要素です。上記の代替手順では、そのような要素が存在する場合は常に右端の要素のインデックスが返されます。^[9] $[1,2,3,4,4,5,6,7]$ $4$ $[1,2,4,4,4,5,6,7]$

左端の要素を見つける手順

左端の要素を見つけるには、次の手順に従います。^[10]

を、をに設定します。 $L$ $0$ $R$ $n$
その間、 $L<R$
1. (中央の要素の位置)をの下限値( より小さいか等しい最大の整数)に加算した値に設定します。 $m$ $L$ ${\frac {RL}{2}}$ ${\frac {RL}{2}}$
2. の場合はに設定します。 $A_{m$ $L$ $m+1$
3. それ以外の場合は、;に設定されます。 $A_{m}\geq T$ $R$ $m$
戻る。 $L$

かつの場合、はに等しい左端の要素です。が配列内に存在しない場合でも、は配列内のの順位、つまり配列内でより小さい要素の数です。 $L<n$ $A_{L}=T$ $A_{L}$ $T$ $T$ $L$ $T$ $T$

floorfloor 関数はどこにありますか。このバージョンの疑似コードは次のとおりです。

関数binary_search_leftmost(A, n, T):
    L := 0
    R := n
    L < Rの場合:
        m := L + floor((R - L) / 2)
        A[m] < Tの場合:
            L := m + 1
        それ以外：
            R := m
    L
を返す

右端の要素を見つける手順

右端の要素を見つけるには、次の手順に従います。^[10]

を、をに設定します。 $L$ $0$ $R$ $n$
その間、 $L<R$
1. (中央の要素の位置)をの下限値( より小さいか等しい最大の整数)に加算した値に設定します。 $m$ $L$ ${\frac {RL}{2}}$ ${\frac {RL}{2}}$
2. の場合はに設定します。 $A_{m}>T$ $R$ $m$
3. それ以外の場合は、;に設定されます。 $A_{m}\leq T$ $L$ $m+1$
戻る。 $R-1$

かつの場合、はに等しい右端の要素です。が配列内にない場合でも、は配列内のより大きい要素の数です。 $R>0$ $A_{R-1}=T$ $A_{R-1}$ $T$ $T$ $nR$ $T$

floorfloor 関数はどこにありますか。このバージョンの疑似コードは次のとおりです。

関数binary_search_rightmost(A, n, T):
    L := 0
    R := n
    L < Rの場合:
        m := L + floor((R - L) / 2)
        A[m] > Tの場合:
            R := m
        それ以外：
            L := m + 1
    R - 1
を返す

おおよその一致

二分探索は近似一致を計算するために応用できます。上記の例では、配列に含まれていないターゲット値について、順位、先行値、後続値、および最近傍値が表示されています。 $5$

{\displaystyle 5} — 二分探索は近似一致を計算するために応用できます。上記の例では、配列に含まれていないターゲット値について、順位、先行値、後続値、および最近傍値が表示されています。 $5$

上記の手順は、完全一致のみを実行し、対象値の位置を見つけます。しかし、二分探索はソートされた配列に対して実行されるため、近似一致を実行するように二分探索を拡張することは簡単です。例えば、二分探索は、与えられた値について、その順位（小さい要素の数）、先行要素（次に小さい要素）、後続要素（次に大きい要素）、および最近傍要素を計算するために使用できます。2つの値の間にある要素の数を検索する範囲クエリは、 2つの順位クエリを使用して実行できます。^[11]

ランク付けクエリは、左端の要素を見つける手順で実行できます。この手順は、目標値より小さい要素の数を返します。 ^[11]
先行クエリはランククエリで実行できます。対象値のランクがの場合、その先行値はです。^[12] $r$ $r-1$
後続クエリでは、右端の要素を見つけるための手順を使用できます。対象値に対してこの手順を実行した結果がである場合、対象値の後続値はです。^[12] $r$ $r+1$
ターゲット値に最も近い近傍は、その前の値または後の値のうち、どちらか近い方になります。
範囲クエリもまた簡単です。^[12] 2つの値の順位が分かれば、最初の値以上で2番目の値より小さい要素の数が、2つの順位の差となります。この数は、範囲の両端を範囲の一部と見なすかどうか、および配列にそれらの両端に一致するエントリが含まれているかどうかに応じて、1ずつ増減できます。^[13]

パフォーマンス

{\displaystyle [20,30,40,50,80,90,100]} — 二分探索を表す木。ここで探索される配列は、目標値はです。 $[20,30,40,50,80,90,100]$ $40$

比較回数の観点から、二分探索の性能は、二分木上での手順の実行を観察することで分析できます。木のルートノードは配列の中央要素です。下半分の中央要素はルートの左の子ノードであり、上半分の中央要素はルートの右の子ノードです。木の残りの部分も同様の方法で構築されます。ルートノードから開始し、対象ノードの値が小さいか大きいかに応じて、左または右のサブツリーを走査します。^[6]^[14]

最悪の場合、二分探索は比較ループを反復します。ここで、は引数以下の最大の整数を返す床関数を表し、は二分対数です。これは、探索がツリーの最深レベルに到達したときに最悪のケースに達するためであり、二分探索ではツリーには常にレベルが存在するためです。 ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ${\textstyle \lfloor \cdot \rfloor }$ ${\textstyle \log _{2}}$ ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$

最悪のケースは、対象要素が配列に存在しない場合にも発生する可能性があります。が2のべき乗より1小さい場合、常にこのようになります。それ以外の場合、探索がツリーの最深レベルに達した場合、探索は反復処理を実行する可能性があります。ただし、探索がツリーの2番目に深いレベルで終了した場合、最悪のケースより1少ない反復処理を実行する可能性があります。^[15] ${\textstyle n}$ ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ${\textstyle \lfloor \log _{2}(n)\rfloor }$

平均的に、各要素が等しく検索される可能性を仮定すると、バイナリサーチは、対象要素が配列内にある場合、反復回数を繰り返す。これは、ほぼ反復回数に等しい。対象要素が配列内にない場合、バイナリサーチは、要素間および要素外の範囲が等しく検索される可能性を仮定すると、平均的に反復回数を繰り返す。^[14] $\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回の反復後に返されます。^[16]

反復処理に関して言えば、要素の比較のみを行う探索アルゴリズムは、平均および最悪のケースにおいて二分探索よりも優れた性能を発揮することはできません。二分探索を表す比較木は、木の最下層より上のすべてのレベルが完全に埋められるため、可能な限りレベル数が少なくなります。^[b]そうでない場合、探索アルゴリズムは反復処理中にいくつかの要素を削除する可能性があり、平均および最悪のケースで必要な反復処理回数が増加します。これは、比較に基づく他の探索アルゴリズムにも当てはまります。これらのアルゴリズムは、一部のターゲット値では高速に処理できるかもしれませんが、すべての要素における平均性能は二分探索よりも劣ります。二分探索は、配列を半分に分割することで、両方のサブ配列のサイズが可能な限り近くなるようにしています。^[14]

空間複雑性

二分探索では、配列のサイズに関わらず、要素へのポインタ（配列インデックスまたはメモリ位置へのポインタ）が3つ必要です。したがって、二分探索の空間計算量は、計算のワードRAMモデルに相当します。 $O(1)$

平均ケースの導出

二分探索で実行される平均反復回数は、各要素が探索される確率に依存する。平均回数は、成功した探索と失敗した探索で異なる。成功した探索では、各要素が等しく探索される可能性が仮定される。失敗した探索では、要素間の間隔と要素外の間隔が等しく探索される可能性が仮定される。成功した探索の平均回数は、すべての要素を正確に1回探索するために必要な反復回数を要素数で割った値である。失敗した探索の平均回数は、すべての間隔内の要素を正確に1回探索するために必要な反復回数を間隔で割った値である。^[14] $n$ $n+1$

成功した検索

二分木表現では、成功した検索はルートからターゲットノードまでのパス（内部パス）で表すことができます。パスの長さは、パスが通過するエッジ（ノード間の接続）の数です。対応するパスの長さが $l で$ あるとすると、検索によって実行される反復回数は、最初の反復をカウントしたものです。内部パスの長さは、すべての一意の内部パスの長さの合計です。ルートからどのノードにもパスは1つしかないため、各内部パスは特定の要素の検索を表します。要素が $n$ 個（正の整数）あり、内部パスの長さがである場合、成功した検索の平均反復回数はとなり、最初の反復をカウントするために1回の反復が追加されます。^[14] $l+1$ $I(n)$ $T(n)=1+{\frac {I(n)}{n}}$

$二分探索は比較を伴う探索に最適なアルゴリズムであるため、この問題はn個の$ ノードを持つすべての二分木の最小内部パス長を計算することに帰着し、これは次の式に等しい：^[17]

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

例えば、7要素の配列では、ルート要素は1回の反復処理を必要とし、ルート要素の下の2つの要素は2回の反復処理を必要とし、その下の4つの要素は3回の反復処理を必要とする。この場合、内部パスの長さは次のようになる。^[17]

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

平均反復回数は平均ケースの式に基づいて算出される。合計は次のように簡略化できる。^[14] $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$

の式をの式に代入すると：^[14] $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$ の場合、これは上記で指定した成功した検索の平均的なケースの式と同等になります。

検索に失敗した

失敗した検索は、ツリーに外部ノードを追加することで表すことができます。これにより、拡張二分木が形成されます。内部ノード、またはツリー内に存在するノードの子ノードが 2 つ未満の場合、各内部ノードが 2 つの子を持つように、外部ノードと呼ばれる追加の子ノードが追加されます。このようにすることで、失敗した検索は、最後の反復で残った単一の要素を親とする外部ノードへのパスとして表すことができます。外部パスは、ルートから外部ノードへのパスです。外部パスの長さは、すべての一意の外部パスの長さの合計です。要素が (正の整数) あり、外部パスの長さがである場合、失敗した検索の平均反復回数は、最初の反復をカウントするために 1 回の反復が追加されます。外部パスの長さはではなくで除算されます。これは、配列の要素間および要素外の間隔を表す外部パスがあるためです。^[14] $n$ $E(n)$ $T'(n)={\frac {E(n)}{n+1}}$ $n+1$ $n$ $n+1$

この問題は同様に、ノードを持つすべての二分木の最小外部パス長を決定する問題に帰着できる。すべての二分木において、外部パス長は内部パス長にを加えた値に等しい。^[17]をに代入すると、次の式が得られる。^[14] $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}$

の式をの式に代入すると、失敗した検索の平均的なケースを決定できます。^[14] $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回の反復が追加され、探索に最大回数の反復が行われることが保証されます。比較ループは最悪の場合でも回しか実行されないため、反復あたりの効率のわずかな向上は、非常に大きな場合を除き、追加の反復を補うものではありません。^[c]^[18]^[19] ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ${\textstyle n}$

追加の考慮事項

比較のコスト

バイナリ検索のパフォーマンスを分析する場合、2 つの要素の比較に必要な時間も考慮する必要があります。整数と文字列の場合、要素のエンコード長 (通常はビット数)が増加すると、必要な時間が直線的に増加します。たとえば、64 ビットの符号なし整数のペアを比較する場合、32 ビットの符号なし整数のペアを比較する場合と比べて最大で 2 倍のビット数を比較する必要があります。最悪のケースは、整数が等しい場合です。大きな整数型や長い文字列など、要素のエンコード長が大きい場合、これは重要になり、要素の比較が高価になります。さらに、浮動小数点値 (実数の最も一般的なデジタル表現) の比較は、整数や短い文字列の比較よりもコストがかかることがよくあります。

浮動小数点数を高速に比較するには、整数として比較します。しかし、この種の比較は全順序付けを形成し、すべての浮動小数点値は互いに異なる値として比較され、それ自体とは同一とみなされます。これは、-0.0 は 0.0 と同じ値として比較されるべきであり、NaN はそれ自体を含む他のどの値とも同一とみなされるべきではないという一般的な比較とは異なります。^[20]^[21]

分岐予測

Steel BankのCommon Lisp貢献者であるPaul Khuong氏によると、二分探索はデータ依存の性質を持つにもかかわらず、分岐予測の誤りが非常に少ないという。これは、二分探索の大部分が分岐ではなく条件付き移動として表現できるためである。これは、ほとんどの対数分割統治探索アルゴリズムにも当てはまる。^[22]

キャッシュの使用

ほとんどのコンピュータアーキテクチャでは、プロセッサは RAMとは別にハードウェアキャッシュを備えています。キャッシュはプロセッサ自体に配置されているため、アクセスははるかに高速ですが、通常、RAM よりもはるかに少ないデータしか保存できません。そのため、ほとんどのプロセッサは、最近アクセスされたメモリ位置を、その近くのメモリ位置と一緒に保存します。たとえば、配列要素にアクセスすると、その要素自体が RAM 内で近くに格納されている要素と一緒に保存されることがあります。これにより、互いにインデックスが近い配列要素への連続アクセスが高速になります（参照の局所性）。ソートされた配列では、要素を順番にアクセスするアルゴリズム（線形探索やハッシュテーブルでの線形プローブなど）とは異なり、配列が大きい場合、バイナリサーチは遠く離れたメモリ位置にジャンプする可能性があります。これにより、ほとんどのシステムで大規模な配列のバイナリサーチの実行時間がわずかに長くなります。^[23]

Paul Khuong 氏は、2 のべき乗サイズの大規模配列（512 KiB 以上）に対するバイナリ検索は、CPU キャッシュの実装方法に起因する新たな問題を引き起こす傾向があると指摘しています。具体的には、トランスレーション・ルックアサイド・バッファ（TLB）は多くの場合、連想メモリ（CAM）として実装されており、その「キー」は通常、要求されたアドレスの下位ビットです。2 のべき乗サイズの配列を検索する場合、同じ下位ビットを持つメモリアドレスにアクセスされる傾向があり、CAM の取得に使用される「キー」との衝突（「エイリアシング」）が発生します。一般的な TLB は 4 ウェイ・アソシエイティブです。つまり、同じ「キー」にヒットするアドレスは最大 4 つまでしか処理できず、それを超えるとTLB スラッシングが発生します。（他のレベルのCPUキャッシュも同様の設定を使用していますが、通常は8または16のウェイ数でより小さな領域を管理するため、影響は少なくなります。）これは、バイナリ検索の分割ポイントをオフセットして、ちょうど真ん中ではなく31 ⁄ 64^{で分割することで防ぐことができます。 [24]}

二分探索と他の手法の比較

ソートされた配列を二分探索で探索する方法は、挿入と削除が検索と交互に行われる場合、非常に非効率的な解決策となり、それぞれの操作に時間がかかります。さらに、ソートされた配列は、特に要素が配列に頻繁に挿入される場合、メモリの使用を複雑化させる可能性があります。^[25]より効率的な挿入と削除をサポートするデータ構造は他にも存在します。二分探索は、完全一致と集合の帰属関係（対象の値が値の集合に含まれるかどうかを判定する）を実行するために使用できます。より高速な完全一致と集合の帰属関係をサポートするデータ構造もあります。しかし、他の多くの検索方式とは異なり、二分探索は効率的な近似一致に使用でき、通常は値自体の型や構造に関わらず、そのような一致を時間内に実行します。^[26]さらに、最小要素と最大要素を見つけるなどの操作は、ソートされた配列に対して効率的に実行できます。^[11] ${\textstyle O(n)}$ ${\textstyle O(\log n)}$

線形探索

線形探索は、目的の値が見つかるまですべてのレコードをチェックする単純な探索アルゴリズムです。線形探索はリンクリスト上で実行でき、配列よりも高速に挿入と削除が可能です。配列が短い場合を除き、ソートされた配列の場合、バイナリ探索は線形探索よりも高速です。ただし、配列は事前にソートされている必要があります。^[d]^[28]クイックソートやマージソートなど、要素の比較に基づくすべてのソートアルゴリズムは、最悪の場合でも少なくとも比較が必要です。 ^[29]線形探索とは異なり、バイナリ探索は効率的な近似マッチングに使用できます。最小要素と最大要素を見つけるなどの操作は、ソートされた配列では効率的に実行できますが、ソートされていない配列では効率的に実行できません。^[30] ${\textstyle O(n\log n)}$

木々

二分探索木は、二分探索の原理に基づいて動作する二分木データ構造です。木内のレコードはソート順に並べられ、木内の各レコードは二分探索に似たアルゴリズムを用いて平均対数時間で検索できます。二分探索木では、挿入と削除も平均対数時間かかります。これは、ソートされた配列の線形時間による挿入と削除よりも高速であり、二分木は範囲検索や近似検索など、ソートされた配列に対して可能なすべての操作を実行できます。^[26]^[31]

しかし、二分探索木は不完全なバランスをとる可能性が高く、二分探索よりもわずかに性能が劣るため、通常は二分探索の方が効率的な探索方法です。これは、自身のノードのバランスをとる二分探索木であるバランス二分探索木にも当てはまります。バランス二分探索木では、階層数が最小限になる木が生成されることは稀だからです。バランス二分探索木を除き、木は内部ノードが少数で子ノードが2つしかなく、著しく不均衡になる場合があり、その結果、平均および最悪の場合の探索時間が比較に近づくことがあります。^[e]二分探索木は、ソートされた配列よりも多くのスペースを必要とします。^[33] ${\textstyle n}$

二分探索木は、ハードディスクに保存された外部メモリ内での高速な検索に適しています。これは、二分探索木がファイルシステム内で効率的に構造化できるためです。B木は、この木構造の手法を一般化したものです。B木は、データベースやファイルシステムなどの長期記憶の整理によく使用されます。^[34]^[35]

ハッシュ

連想配列を実装する場合、ハッシュテーブル（ハッシュ関数を使用してキーをレコードにマッピングするデータ構造）は、ソートされたレコード配列のバイナリ検索よりも一般的に高速です。^[36]ほとんどのハッシュテーブルの実装では、平均して償却定数時間しかかかりません。 ^[f]^[38]しかし、ハッシュは、次に小さいキー、次に大きいキー、最も近いキーを計算するなどの近似一致には役立ちません。失敗した検索で得られる情報は、ターゲットがどのレコードにも存在しないということだけだからです。^[39]バイナリ検索はこのような一致に最適で、対数時間で実行します。バイナリ検索は近似一致もサポートしています。最小要素と最大要素を見つけるなどの一部の操作は、ソートされた配列では効率的に実行できますが、ハッシュテーブルでは効率的に実行できません。^[26]

セットメンバーシップアルゴリズム

検索に関連する問題として、集合の帰属関係があります。二分探索のような検索を行うアルゴリズムは、集合の帰属関係にも適用できます。集合の帰属関係に特に適したアルゴリズムも存在します。ビット配列は最も単純で、キーの範囲が限られている場合に便利です。ビット配列はビットの集合をコンパクトに格納し、各ビットはキーの範囲内の単一のキーを表します。ビット配列は非常に高速で、処理時間はわずかです。^[40] Judy1型のJudy配列は、 64ビットのキーを効率的に処理します。^[41] ${\textstyle O(1)}$

近似値を求める場合、ハッシュに基づく別の確率的データ構造であるブルームフィルタは、ビット配列と複数のハッシュ関数を用いてキーをエンコードし、キーセットを保存します。ブルームフィルタは、ほとんどの場合、ビット配列よりもはるかに空間効率が高く、速度もそれほど遅くありません。ハッシュ関数を用いると、メンバーシップクエリはわずか1000秒で済みます。しかし、ブルームフィルタは誤検出の問題を抱えています。^[g]^[h]^[43] ${\textstyle k}$ ${\textstyle O(k)}$

その他のデータ構造

ソート済み配列に対して実行可能な検索操作とその他の操作の両方において、場合によっては二分探索よりも性能が向上するデータ構造が存在します。例えば、検索、近似一致、ソート済み配列に対して実行可能な操作は、ファン・エムデ・ボアズ木、融合木、トライ、ビット配列といった特殊なデータ構造では二分探索よりも効率的に実行できます。これらの特殊なデータ構造は通常、特定の属性を持つキー（通常は小さな整数のキー）の特性を利用しているため高速であり、その属性を持たないキーでは時間や空間を消費します。^[26]キーを順序付けできる限り、これらの操作はキーの種類に関わらず、ソート済み配列上で少なくとも効率的に実行できます。Judy配列などの一部の構造では、効率性と近似一致の実行能力を維持しながらこの問題を軽減するために、複数のアプローチを組み合わせて使用しています。^[41]

バリエーション

均一二分探索

均一二分探索は、下限と上限の代わりに、現在の反復から次の反復までの中央の要素のインデックスの差を格納します。差を含むルックアップテーブルは事前に計算されます。たとえば、検索する配列が $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]$ の場合、中央の要素 ( ) は $6$ になります。この場合、左のサブ配列 ( $[1, 2, 3, 4, 5]$ )の中央の要素は $3で、右のサブ配列 ($ $[7, 8, 9, 10, 11]$ )の中央の要素は $9$ です。均一二分探索では、両方のインデックスが $6$ から同じ量だけ異なるため、値 $3が格納されます。$ ^[44]検索空間を減らすために、アルゴリズムは中央の要素のインデックスにこの変化を加算または減算します。一様二分探索は、 10進コンピュータなど、中間点を計算するのが非効率なシステムではより高速になる可能性がある。^[45] $m$

指数探索

指数探索は、二分探索を無限リストに拡張したものです。指数探索は、まず、インデックスが2のべき乗であり、かつ目標値よりも大きい最初の要素を見つけます。その後、そのインデックスを上限として二分探索に切り替えます。探索は二分探索を開始する前に反復回数、二分探索の最大反復回数を必要とします。ここで、は目標値の位置です。指数探索は有限リストでも機能しますが、目標値が配列の先頭付近にある場合にのみ、二分探索よりも優れたものとなります。^[46] ${\textstyle \lfloor \log _{2}x+1\rfloor }$ ${\textstyle \lfloor \log _{2}x\rfloor }$ ${\textstyle x}$

補間検索

補間探索では、中間点を計算する代わりに、配列内の最小要素と最大要素、および配列の長さを考慮して、目標値の位置を推定します。これは、中間点が多くの場合最良の推定値ではないという前提に基づいています。例えば、目標値が配列内の最大要素に近い場合、配列の末尾付近に位置する可能性が高くなります。^[47]

一般的な補間関数は線形補間である。が配列、がそれぞれ下限値と上限値、が目標値である場合、目標値はとの間の約 0.5 の近辺にあると推定される。線形補間が使用され、配列要素の分布が均一またはほぼ均一である場合、補間探索は比較を行う。^[47]^[48]^[49] $A$ $L,R$ $T$ $(T-A_{L})/(A_{R}-A_{L})$ $L$ $R$ ${\textstyle O(\log \log n)}$

実際には、補間探索は小さな配列では二分探索よりも遅くなります。これは、補間探索には追加の計算が必要となるためです。補間探索の時間計算量は二分探索よりも緩やかに増加しますが、これは大きな配列の場合の追加計算を補うだけです。^[47]

部分的カスケーディング

分数カスケーディングは、複数のソート済み配列における同一要素の二分探索を高速化する手法です。各配列を個別に探索すると時間がかかります（配列の数）。分数カスケーディングでは、各配列に各要素と他の配列における位置に関する特定の情報を格納することで、この時間を短縮します。^[50]^[51] ${\textstyle O(k\log n)}$ ${\textstyle k}$ ${\textstyle O(k+\log n)}$

分数カスケーディングは、もともと様々な計算幾何学問題を効率的に解くために開発されました。分数カスケーディングは、データマイニングやインターネットプロトコルルーティングなど、他の分野にも応用されています。^[50]

グラフへの一般化

二分探索は、ターゲット値が配列要素ではなく頂点に格納される特定の種類のグラフで機能するように一般化されています。二分探索木はこうした一般化の 1 つです。木内の頂点 (ノード) が照会されると、アルゴリズムは頂点がターゲットであるか、そうでない場合はターゲットがどのサブツリーに位置するかを学習します。ただし、これは次のようにさらに一般化できます。無向で正の重みを持つグラフとターゲット頂点が与えられると、アルゴリズムは頂点を照会したときにその頂点がターゲットと等しいか、照会された頂点からターゲットへの最短パス上にある接続エッジが与えられるかを学習します。標準的な二分探索アルゴリズムは、グラフがパスである場合に単純に当てはまります。同様に、二分探索木は、照会された頂点がターゲットと等しくない場合に左または右のサブツリーへのエッジが与えられる場合です。すべての無向で正の重みを持つグラフに対して、最悪の場合でもクエリ内のターゲット頂点を見つけるアルゴリズムが存在します。 ^[52] $O(\log n)$

ノイズの多い二分探索

ノイズ付き二分探索アルゴリズムは、配列の要素をアルゴリズムが確実に比較できない場合に解決します。各要素のペアに対して、アルゴリズムが誤った比較を行う一定の確率があります。ノイズ付き二分探索は、得られた位置の信頼性を制御する所定の確率で、ターゲットの正しい位置を見つけることができます。すべてのノイズ付き二分探索手順は、平均して少なくとも回の比較を行う必要があります。ここで、は二分エントロピー関数であり、は手順が誤った位置を生成する確率です。^[53]^[54]^[55]ノイズ付き二分探索問題は、答えが間違っている可能性がある20の質問の変種であるレーニイ・ウラムゲーム[ ^56]のケースと考えることができます。^[57] $(1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}$ $H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)$ $\tau$

量子二分探索

古典的コンピュータは、二分探索を実行する際に、最悪の場合でも正確に回しか反復できないという制約を受ける。二分探索のための量子アルゴリズムも、クエリ（古典的手順の反復を表す）の割合に制限されるが、定数係数は 1 未満であるため、量子コンピュータでは時間計算量が低くなる。正確な量子二分探索手順（つまり、常に正しい結果を生成する手順）は、最悪の場合でも少なくとも回（は自然対数）のクエリを必要とする。^[58]最悪の場合でも回で実行される正確な量子二分探索手順が存在する。 ^[59]これと比較して、グローバーのアルゴリズムは、順序付けられていない要素のリストを検索するための最適な量子アルゴリズムであり、クエリを必要とする。^[60] ${\textstyle \lfloor \log _{2}n+1\rfloor }$ ${\textstyle \log _{2}n}$ ${\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年頃のバビロンのイナキビト・アヌ粘土板である。この粘土板には約500個の60進数とその逆数が辞書式順序で記載されており、特定の項目の検索が容易になった。さらに、エーゲ海諸島では、名前の最初の文字で並べ替えられたリストがいくつか発見されている。 1286年に完成したラテン語辞典『カトリコン』は、単語を最初の数文字だけでなくアルファベット順に並べ替える規則を記述した最初の著作であった。^[9]

1946年、ジョン・モークリーは、ムーア・スクールの講義の一部として初めてバイナリ検索について言及しました。これは、コンピューターに関する大学の重要かつ基礎的なコースでした。 ^[9] 1957年、ウィリアム・ウェズリー・ピーターソンは、補間検索の最初の方法を発表しました。^[9]^[61]公開されたバイナリ検索アルゴリズムはすべて、長さが2の累乗より1小さい配列に対してのみ機能しました^[i] 1960年にデリック・ヘンリー・レーマーがすべての配列で機能するバイナリ検索アルゴリズムを発表しました。^[63] 1962年、ヘルマン・ボッテンブルックは、等価性の比較を最後に置くバイナリ検索のALGOL 60実装を発表しました。これにより、反復の平均回数は1つ増えますが、反復ごとの比較回数は1つに減ります。^[8]均一二分探索は1971年にスタンフォード大学のAKチャンドラによって開発されました^。[9] 1986年にバーナード・チャゼルとレオニダス・J・ギバスは計算幾何学における多くの探索問題を解く方法として分数カスケーディングを導入しました。^[50]^[64]^[65]

実装上の問題

二分探索の基本的な考え方は比較的単純ですが、詳細は驚くほど複雑になることがあります。

— ドナルド・クヌース^[2]

ジョン・ベントレーがプロのプログラマー向けのコースで二分探索の問題を出題したところ、数時間取り組んでも90%の解答が正解に至らなかった。その主な原因は、間違った実装では実行に失敗したり、稀なエッジケースで間違った答えが返ったりすることだった。^[66] 1988年に発表された調査では、正確なコードは20冊の教科書のうち5冊にしか載っていないことが示されている。^[67]さらに、ベントレーが1986年に出版した著書「Programming Pearls 」で発表した二分探索の実装にはオーバーフローエラーがあり、20年以上も検出されなかった。Javaプログラミング言語ライブラリの二分探索の実装にも、9年以上にわたって同じオーバーフローバグがあった。^[68]

実際の実装では、インデックスを表す変数は固定サイズ（整数）であることが多く、非常に大きな配列では算術オーバーフローが発生する可能性があります。範囲の中点をと計算すると、とが範囲内であっても、の値は中点を格納するために使用されるデータ型の整数の範囲を超える可能性があります。とが非負の場合、中点をと計算することでこれを回避できます。^[69] ${\frac {L+R}{2}}$ $左+右$ $L$ $R$ $L$ $R$ $L+{\frac {RL}{2}}$

ループの終了条件が正しく定義されていない場合、無限ループが発生する可能性があります。を超えると検索は失敗となり、その旨を伝える必要があります。さらに、目的の要素が見つかった時点でループを終了させる必要があります。このチェックを最後に移動させる実装の場合は、最後に検索が成功したか失敗したかを確認するチェックを配置する必要があります。ベントレーは、二分探索を誤って実装したプログラマーのほとんどが、終了条件の定義に誤りを犯していることを発見しました。^[8]^[70] $L$ $R$

図書館サポート

多くの言語の標準ライブラリにはバイナリ検索ルーチンが含まれています。

C言語は標準ライブラリに関数を提供しており、公式標準では必須ではないものの、通常はバイナリサーチで実装されている。^[71]bsearch()
C++の標準ライブラリは関数binary_search()、、lower_bound()を提供していますupper_bound()。^[72]C++20ライブラリを使用すると、範囲にとして適用できます。equal_range() std::rangesstd::ranges::binary_search()
Dの標準ライブラリPhobosは、モジュールでは、ランダムアクセスを提供する範囲に対してデフォルトでバイナリ検索技術を使用する、、、およびメソッドを持つstd.range型SortedRange（sort()およびassumeSorted()関数によって返される）を提供します。 ^[73]contains()equaleRange()lowerBound()trisect()
COBOLはCOBOLの順序付きテーブルに対してバイナリ検索を実行するための動詞を提供していますSEARCH ALL。^[74]
Goのsort標準ライブラリパッケージには、一般的な二分探索を実装する関数Search、、、および、SearchIntsに加えて、それぞれ整数、浮動小数点数、文字列のスライスを検索するための特定の実装が含まれています。^[75]SearchFloat64sSearchStrings
Javaは、Java配列とJava配列上でバイナリ検索を実行するためのオーバーロードされた静的メソッドのセットをbinarySearch()クラスArraysとCollections標準パッケージで提供しています。^[76]^[77]java.utilList
Microsoft .NET Framework 2.0 は、コレクション基本クラスにおいて二分探索アルゴリズムの静的ジェネリック版を提供しています。例としては、System.Arrayのメソッドが挙げられますBinarySearch<T>(T[] array, T value)。^[78]
Objective-Cでは、CocoaフレームワークがMac OS X 10.6以降でNSArray -indexOfObject:inSortedRange:options:usingComparator:メソッドを提供しています。^[79] AppleのCore Foundation CフレームワークにもCFArrayBSearchValues()関数が含まれています。^[80]
Pythonはbisect、挿入のたびにリストをソートすることなく、リストをソートされた順序で保持するモジュールを提供しています。 ^[81]
RubyのArrayクラスにはbsearch近似マッチングを組み込んだメソッドが含まれています。^[82]
Rustのスライスプリミティブは、、、、を提供しますbinary_search()。[ 83 ^]binary_search_by()binary_search_by_key()partition_point()

参照

二分法 - 関数の零点を見つけるアルゴリズム - 実数の方程式を解くのと同じ考え方
乗法二分探索 – 簡略化された中間点計算による二分探索のバリエーション

注釈と参考文献

この記事は2018年にWikiJournal of Scienceに外部学術査読のために提出されました（査読者レポート）。更新されたコンテンツは、CC-BY-SA-3.0ライセンス（ 2019年）に基づきWikipediaページに再統合されました。査読済み版は、 Anthony Lin; et al. (2019年7月2日). "Binary search algorithm" (PDF) . WikiJournal of Science . 2 (1): 5. doi : 10.15347/WJS/2019.005 . ISSN 2470-6345. Wikidata Q81434400. です。

注記

^ はBig O記法であり、は対数です。Big O記法では、対数の底は重要ではありません。なぜなら、ある底の対数はすべて、別の底の対数の定数倍となるからです。つまり、となります。ここでは定数です。 $O$ $\log$ $\log_{b}(n)=\log_{k}(n)\div \log_{k}(b)$ $\log _{k}(b)$
^ 比較のみに基づく探索アルゴリズムは、バイナリ比較ツリーを使用して表現できます。内部パスとは、ルートから既存のノードへの任意のパスのことです。を内部パスの長さ、つまりすべての内部パスの長さの合計とします。各要素が等しく探索される可能性がある場合、平均的なケースは、またはツリーのすべての内部パスの長さの平均に1を加算した値になります。これは、内部パスが、探索アルゴリズムがターゲットと比較する要素を表しているためです。これらの内部パスの長さは、ルートノード以降の反復回数を表します。これらの長さの平均をルートでの1回の反復に追加すると、平均的なケースが得られます。したがって、平均比較回数を最小化するには、内部パスの長さを最小化する必要があります。バイナリ探索のツリーは内部パスの長さを最小化することがわかります。Knuth 1998 は、外部ノード(子を持たないノード) がツリーの連続する2つのレベル内にある場合、外部パスの長さ (既存の各ノードの両方の子が存在するすべてのノードにわたるパスの長さ) が最小化されることを証明しました。これは内部パスにも当てはまります。内部パスの長さは外部パスの長さと線形関係にあるからです。任意のノードツリーについて、各サブツリーのノード数が同数の場合、つまり各反復処理で配列が半分に分割される場合、外部ノードとその内部親ノードは2つのレベル内にあります。したがって、二分探索は比較ツリーの内部パスの長さが可能な限り短くなるため、平均比較回数を最小限に抑えることができます。^[14] $I$ $1+{\frac {I}{n}}$ $I$ $I$ $E$ $n$ $I=E-2n$
^ クヌース（Knuth）は1998年、通常のコンピュータをモデル化して設計したMIXコンピュータモデルを用いて、このバリエーションの探索成功の平均実行時間が、通常の二分探索の単位時間あたり数単位であることを示した。このバリエーションの計算時間の増加はわずかに緩やかであるが、初期計算量の増加という代償を払う。^[18] ${\textstyle 17.5\log _{2}n+17}$ ${\textstyle 18\log _{2}n-16}$
^ Knuth 1998は、これら2つの探索アルゴリズムの形式的な時間性能分析を行った。Knuthが通常のコンピュータの表現として設計したMIXコンピュータでは、二分探索は成功に平均単位の時間がかかるのに対し、リストの末尾にセンチネルノードを配置した線形探索は単位の時間がかかる。線形探索は計算量が最小限であるため初期の複雑度は低いが、すぐに二分探索の複雑度を上回る。MIXコンピュータでは、二分探索がセンチネルノードを配置した線形探索を上回るのは、次の場合のみである。^[14]^[27] ${\textstyle 18\log n-16}$ ${\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}}$ ${\textstyle n>44}$
^ 値をソート順に、または最低・最高のキーパターンを交互に挿入すると、平均および最悪の場合の検索時間を最大化するバイナリ検索ツリーが生成されます。^[32]
^ いくつかのハッシュテーブル実装では、定数時間での検索が保証されている。^[37]
^ これは、ハッシュ関数が特定のキーに対して指し示すすべてのビットを単に設定するだけで、1つ以上の関数に対して共通のハッシュ位置を持つ他のキーのクエリに影響を与える可能性があるためです。^[42]
^ ブルームフィルタには、複雑さを改善したり削除をサポートしたりする改良版が存在する。例えば、カッコウフィルタはカッコウハッシュを利用してこれらの利点を得ている。^[42]
^ つまり、長さ1、3、7、15、31の配列... ^[62]

引用

^ Williams, Jr., Louis F. (1976年4月22日). 半区間探索（二分探索）法の修正. Proceedings of the 14th ACM Southeast Conference. ACM. pp. 95– 101. doi : 10.1145/503561.503582 . 2017年3月12日時点のオリジナルよりアーカイブ。 2018年6月29日閲覧。
^ ab Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「バイナリ検索」。
^ バターフィールド＆ンゴンディ 2016、p. 46.
^ Cormen et al. 2009, p.39.
^ Weisstein, Eric W.「二分探索」。MathWorld。
^ ab Flores, Ivan; Madpis, George (1971年9月1日). 「密な順序付きリストの平均二分探索長」Communications of the ACM . 14 (9): 602– 603. doi : 10.1145/362663.362752 . ISSN 0001-0782. S2CID 43325465.
^ abc Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「アルゴリズムB」。
^ abcd Bottenbruch, Hermann (1962年4月1日). 「ALGOL 60の構造と利用」. Journal of the ACM . 9 (2): 161– 221. doi : 10.1145/321119.321120 . ISSN 0004-5411. S2CID 13406983.手順は、p. 214 (§43) の「二分探索プログラム」に記載されています。
^ abcdef Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「履歴と参考文献」。
^ ab 笠原 & 森下 2006, pp. 8–9.
^ abc Sedgewick & Wayne 2011、§3.1、サブセクション「ランクと選択」。
^ abc ゴールドマン＆ゴールドマン2008、pp.461-463。
^ Sedgewick & Wayne 2011、§3.1、サブセクション「範囲クエリ」。
^ abcdefghijkl Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「バイナリ検索のさらなる分析」。
^ Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、「定理B」。
^ チャン 2003、169ページ。
^ abc Knuth 1997、§2.3.4.5（「パス長」）。
^ ab Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「演習 23」。
^ Rolfe, Timothy J. (1997). 「二分探索における比較の解析的導出」. ACM SIGNUM ニュースレター. 32 (4): 15– 19. doi : 10.1145/289251.289255 . S2CID 23752485.
^ Herf, Michael (2001年12月). 「radix tricks」.ステレオプシス: グラフィックス.
^ "f32、f64用のtotal_cmpを実装 by golddranks · プルリクエスト#72568 · rust-lang/rust". GitHub .– IEEE 754-2008および-2019からの関連引用が含まれています。type-punの実装と説明が含まれています。
^ 「バイナリ検索は分岐予測ミスを*排除*します - Paul Khuong: some Lisp」pvk.ca。
^ Khuong, Paul-Virak; Morin, Pat (2017). 「比較ベース検索のための配列レイアウト」. Journal of Experimental Algorithmics . 22. Article 1.3. arXiv : 1509.05053 . doi :10.1145/3053370. S2CID 23752485.
^ 「バイナリ検索はキャッシュの病的なケースです - Paul Khuong: いくつかのLisp」pvk.ca。
^ Knuth 1997、§2.2.2（「順次割り当て」）。
^ abcd Beame, Paul; Fich, Faith E. (2001). 「先行問題および関連問題に対する最適境界」. Journal of Computer and System Sciences . 65 (1): 38– 72. doi : 10.1006/jcss.2002.1822 .
^ Knuth 1998、「演習 5」の解答 (§6.2.1)。
^ Knuth 1998、§6.2.1（「順序付きテーブルの検索」）。
^ Knuth 1998、§5.3.1（「最小比較ソート」）。
^ Sedgewick & Wayne 2011、§3.2（「順序付きシンボルテーブル」）。
^ Sedgewick & Wayne 2011、§3.2（「二分探索木」）、サブセクション「順序ベースの方法と削除」。
^ Knuth 1998、§6.2.2（「二分木探索」）、サブセクション「しかし、最悪のケースはどうなるか？」。
^ Sedgewick & Wayne 2011、§3.5（「アプリケーション」）、「どのシンボルテーブル実装を使用すればよいですか？」
^ Knuth 1998、§5.4.9（「ディスクとドラム」）。
^ Knuth 1998、§6.2.4（「マルチウェイツリー」）。
^ Knuth 1998、§6.4（「ハッシュ」）。
^ Knuth 1998、§6.4（「ハッシュ」）、サブセクション「履歴」。
^ ディーツフェルビンガー、マーティン;アンナ・カーリン;クルト州;マイヤー・アウフ・デア・ハイデ、フリードヘルム。ローナート、ハンス。タージャン、ロバート E. (1994 年 8 月)。「動的完全ハッシュ: 上限と下限」。SIAM ジャーナルオンコンピューティング。23 (4): 738–761。土井:10.1137/S0097539791194094。
^ Morin, Pat. 「ハッシュテーブル」(PDF) . p. 1. 2022年10月9日時点のオリジナルよりアーカイブ(PDF) . 2016年3月28日閲覧。
^ Knuth 2011、§7.1.3（「ビット単位のトリックとテクニック」）。
^ ab Silverstein, Alan, Judy IV shop manual (PDF)、Hewlett-Packard、pp. 80– 81、 2022年10月9日時点のオリジナルよりアーカイブ(PDF)
^ ab Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014).カッコウフィルタ：実質的にブルームよりも優れている. Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. pp. 75– 88. doi : 10.1145/2674005.2674994 .
^ Bloom, Burton H. (1970). 「許容誤差を考慮したハッシュ符号化における空間／時間トレードオフ」Communications of the ACM . 13 (7): 422– 426. CiteSeerX 10.1.1.641.9096 . doi :10.1145/362686.362692. S2CID 7931252.
^ Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「重要なバリエーション」。
^ Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「アルゴリズムU」。
^ モファット＆ターピン 2002年、33ページ。
^ abc Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「補間検索」。
^ Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「演習22」。
^ Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). 「補間探索—log log n探索」Communications of the ACM . 21 (7): 550– 553. doi : 10.1145/359545.359557 . S2CID 11089655.
^ abc Chazelle, Bernard ; Liu, Ding (2001年7月6日).高次元における交差探索と分数カスケーディングの下限値. 第33回ACM計算理論シンポジウム. ACM. pp. 322– 329. doi :10.1145/380752.380818. ISBN 978-1-58113-349-3. 2018年6月30日閲覧。
^ Chazelle, Bernard ; Liu, Ding (2004年3月1日). 「高次元における交差探索と分数カスケーディングの下限値」(PDF) . Journal of Computer and System Sciences . 68 (2): 269– 284. CiteSeerX 10.1.1.298.7772 . doi :10.1016/j.jcss.2003.07.003. ISSN 0022-0000. 2022年10月9日時点のオリジナルよりアーカイブ(PDF) . 2018年6月30日閲覧。
^ Emamjomeh-Zadeh, Ehsan; Kempe, David; Singhal, Vikrant (2016).グラフにおける決定論的および確率的二分探索. 第48回ACMコンピューティング理論シンポジウム. pp. 519– 532. arXiv : 1503.00805 . doi :10.1145/2897518.2897656.
^ ベン＝オール、マイケル、ハシディム、アビナタン (2008). 「ベイズ学習器はノイズのある二分探索に最適であり（量子探索にも非常に有効である）」(PDF) .第49回コンピュータサイエンス基礎シンポジウム. pp. 221– 230. doi :10.1109/FOCS.2008.58. ISBN 978-0-7695-3436-72022年10月9日時点のオリジナルよりアーカイブ（PDF）。
^ Pelc, Andrzej (1989). 「既知のエラー確率による検索」.理論計算機科学. 63 (2): 185– 202. doi : 10.1016/0304-3975(89)90077-7 .
^ Rivest, Ronald L. ; Meyer, Albert R. ; Kleitman, Daniel J. ; Winklmann, K.バイナリ検索手順におけるエラーへの対処。第10回ACMコンピューティング理論シンポジウム。doi : 10.1145/800133.804351。
^ ペルク、アンジェイ (2002). 「エラーのあるゲームを探す ― 嘘つきへの対処の50年」理論計算機科学. 270 ( 1– 2): 71– 109. doi : 10.1016/S0304-3975(01)00303-6 .
^ アルフレッド・レンイ (1961). 「情報理論の問題について」。マジャール語 Tudományos Akadémia Matematikai Kutató Intézetének Közleményei (ハンガリー語)。6 : 505–516。MR 0143666 。
^ Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). 「順序付き探索、ソート、要素の明確さに関する量子計算量」. Algorithmica . 34 (4): 429– 448. arXiv : quant-ph/0102078 . doi :10.1007/s00453-002-0976-3. S2CID 13717616.
^ Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A. (2007). 「半正定値計画法による順序探索問題に対する量子アルゴリズム」. Physical Review A. 75 ( 3). 032335. arXiv : quant-ph/0608161 . Bibcode :2007PhRvA..75c2335C. doi :10.1103/PhysRevA.75.032335. S2CID 41539957.
^ Grover, Lov K. (1996).データベース検索のための高速量子力学アルゴリズム. 第28回ACMコンピューティング理論シンポジウム. フィラデルフィア, PA. pp. 212– 219. arXiv : quant-ph/9605043 . doi :10.1145/237814.237866.
^ ピーターソン、ウィリアム・ウェスレー(1957). 「ランダムアクセスストレージのアドレス指定」. IBM Journal of Research and Development . 1 (2): 130– 146. doi :10.1147/rd.12.0130.
^ “2 ⁿ −1”. OEIS A000225. 2016年6月8日アーカイブ. 2016年5月7日閲覧。
^ レーマー、デリック (1960). 「コンピュータに組み合わせ論的トリックを教える」.組み合わせ解析. 応用数学シンポジウム論文集. 第10巻. pp. 180– 181. doi : 10.1090/psapm/010/0113289 . ISBN 9780821813102. MR 0113289。 {{cite book}}:ISBN / 日付の非互換性（ヘルプ）
^ Chazelle, Bernard ; Guibas, Leonidas J. (1986). 「フラクショナルカスケーディング：I. データ構造化手法」(PDF) . Algorithmica . 1 ( 1–4 ): 133– 162. CiteSeerX 10.1.1.117.8349 . doi :10.1007/BF01840440. S2CID 12745042.
^ Chazelle, Bernard ; Guibas, Leonidas J. (1986)、「分数カスケーディング：II. 応用」（PDF）、Algorithmica、1（1–4）：163–191、doi：10.1007/BF01840441、S2CID 11232235
^ Bentley 2000、§4.1（「バイナリ検索の課題」）。
^ パティス、リチャード・E. (1988). 「二分探索における教科書の誤り」. SIGCSE Bulletin . 20 : 190–194 . doi :10.1145/52965.53012.
^ Bloch, Joshua (2006年6月2日). 「Extra, extra – read all about it: almost all binarysearchs and mergesorts are broken. Google Research Blog . 2016年4月1日時点のオリジナルよりアーカイブ。 2016年4月21日閲覧。
^ Ruggieri, Salvatore (2003). 「2つの整数の半和の計算について」(PDF) . Information Processing Letters . 87 (2): 67– 71. CiteSeerX 10.1.1.13.5631 . doi :10.1016/S0020-0190(03)00263-1. 2006年7月3日時点のオリジナルよりアーカイブ(PDF) . 2016年3月19日閲覧.
^ Bentley 2000、§4.4（「原則」）。
^ "bsearch – ソートされたテーブルのバイナリ検索". The Open Group Base仕様（第7版）. The Open Group . 2013年. 2016年3月21日時点のオリジナルよりアーカイブ。 2016年3月28日閲覧。
^ Stroustrup 2013、945ページ。
^ “std.range - Dプログラミング言語”. dlang.org . 2020年4月29日閲覧。
^ Unisys (2012)、COBOL ANSI-85プログラミングリファレンスマニュアル、第1巻、pp. 598– 601
^ “Package sort”. Goプログラミング言語. 2016年4月25日時点のオリジナルよりアーカイブ。 2016年4月28日閲覧。
^ "java.util.Arrays". Java Platform Standard Edition 8 ドキュメント. Oracle Corporation . 2016年4月29日時点のオリジナルよりアーカイブ。2016年5月1日閲覧。
^ "java.util.Collections". Java Platform Standard Edition 8 ドキュメント. Oracle Corporation . 2016年4月23日時点のオリジナルよりアーカイブ。2016年5月1日閲覧。
^ “List<T>.BinarySearch メソッド (T)”. Microsoft Developer Network . 2016年5月7日時点のオリジナルよりアーカイブ。2016年4月10日閲覧。
^ "NSArray". Mac Developer Library . Apple Inc. 2016年4月17日時点のオリジナルよりアーカイブ。2016年5月1日閲覧。
^ "CFArray". Mac Developer Library . Apple Inc. 2016年4月20日時点のオリジナルよりアーカイブ。2016年5月1日閲覧。
^ “8.6. bisect — 配列二分アルゴリズム”. Python標準ライブラリ. Python Software Foundation. 2018年3月25日時点のオリジナルよりアーカイブ。 2018年3月26日閲覧。
^ フィッツジェラルド 2015、152ページ。
^ 「プリミティブ型スライス」. Rust標準ライブラリ. Rust Foundation. 2024年. 2024年5月25日閲覧。

出典

ベントレー、ジョン（2000年）『プログラミングの真珠』（第2版）Addison-Wesley . ISBN 978-0-201-65788-3。
バターフィールド、アンドリュー、ンゴンディ、ジェラード・E. (2016). 『コンピュータサイエンス辞典（第7版）』オックスフォード大学出版局（英国） . ISBN 978-0-19-968897-5。
Chang, Shi-Kuo (2003).データ構造とアルゴリズム. ソフトウェア工学と知識工学. 第13巻. シンガポール: World Scientific . ISBN 978-981-238-348-8。
トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009)。アルゴリズム入門(第 3 版)。 MIT プレスとマグロウヒル。ISBN 978-0-262-03384-8。
フィッツジェラルド、マイケル (2015). Rubyポケットリファレンス. セバストーポル、カリフォルニア州: O'Reilly Media . ISBN 978-1-4919-2601-7。
ゴールドマン、サリー・A. ; ゴールドマン、ケネス・J. (2008). Javaを用いたデータ構造とアルゴリズムの実践ガイド. フロリダ州ボカラトン: CRC Press . ISBN 978-1-58488-455-2。
笠原正弘、森下真一 (2006).大規模ゲノム配列処理. ロンドン、英国: インペリアル・カレッジ・プレス. ISBN 978-1-86094-635-6。
ドナルド・クヌース（1997年）『基本アルゴリズム』『コンピュータプログラミングの技法』第1巻（第3版）『アディソン・ウェズリー・プロフェッショナル』（マサチューセッツ州レディング）ISBN 978-0-201-89683-1。
ドナルド・クヌース（1998年）『ソートと検索』『コンピュータプログラミングの芸術』第3巻（第2版）『アディソン・ウェズリー・プロフェッショナル社』（マサチューセッツ州レディング）ISBN 978-0-201-89685-5。
ドナルド・クヌース（2011年）『組み合わせアルゴリズム』『コンピュータプログラミングの技法』第4A巻（第1版）『アディソン・ウェズリー・プロフェッショナル』（マサチューセッツ州レディング）ISBN 978-0-201-03804-0。
Moffat, Alistair; Turpin, Andrew (2002).圧縮および符号化アルゴリズム. ハンブルク, ドイツ: Kluwer Academic Publishers. doi :10.1007/978-1-4615-0935-6. ISBN 978-0-7923-7668-2。
セジウィック, ロバート; ウェイン, ケビン (2011). 『アルゴリズム』（第4版）. アッパーサドルリバー, ニュージャージー州: アディソン・ウェスリー・プロフェッショナル. ISBN 978-0-321-57351-3。要約版ウェブ版 ; 書籍版。
ストロウストルップ、ビャーネ(2013). 『C++プログラミング言語（第4版）』アッパーサドルリバー、ニュージャージー州: アディソン・ウェズリー・プロフェッショナル. ISBN 978-0-321-56384-2。

外部リンク

Wikibookアルゴリズム実装には、二分探索に関するページがあります。

NISTアルゴリズムとデータ構造辞書: 二分探索
C言語による様々なバイナリサーチ実装の比較とベンチマーク 2019年9月25日アーカイブWayback Machine