二分探索

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

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

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

アルゴリズム

二分探索は、ソートされた配列に対して機能します。二分探索は、配列の中央にある要素と目標値を比較することから始まります。目標値が要素と一致する場合、配列内のその位置が返されます。目標値が要素より小さい場合、探索は配列の下半分で続行されます。目標値が要素より大きい場合、探索は配列の上半分で続行されます。このようにして、アルゴリズムは各反復で目標値が存在しない半分を排除します。^{[ 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$ プラス床 $\displaystyle {\frac {RL}{2}}}$ これは、以下の最大の整数です。 $\displaystyle {\frac {RL}{2}}}$ 。
もし $A_{m}<T$ 、セット $L$ に $m+1$ そしてステップ2に進みます。
もし $A_{m}>T$ 、セット $R$ に $m-1$ そしてステップ2に進みます。
今 $A_{m}=T$ 検索が完了しました。 $m$ 。

この反復手順では、2 つの変数を使用して検索範囲を追跡します。 $L$ そして $R$ 手順は擬似コードで次のように表すことができ、変数名と型は上記と同じで、floorは床関数、はunsuccessful検索の失敗を示す特定の値を参照します。^{[ 7 ]}

関数binary_search(A, n, T)は L := 0 R := n − 1 while L ≤ R do m := L + floor((R - L) / 2) A[m] < Tの場合 L := m + 1 else if A[m] > T then R := m − 1 else : return m return unuccessful

あるいは、アルゴリズムは天井を取るかもしれない $\displaystyle {\frac {RL}{2}}}$ 配列内に目的の値が複数回出現する場合、結果が変わる可能性があります。

代替手順

上記の手順では、アルゴリズムは中間要素（ $m$ ）は目標値と等しい（ $T$ ）各イテレーションで。一部の実装では、各イテレーション中にこのチェックを省略します。アルゴリズムは、要素が 1 つだけ残っているとき（ $L=R$ これにより、1回の反復で1回の比較が省略され、平均して1回多く反復するだけで済むため、比較ループが高速化されます。^{[ 8 ]}

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

セット $L$ に $0$ そして $R$ に $n-1$ 。
その間 $L\neq R$ $L\neq R$ 、
1. セット $m$ （中央要素の位置） $L$ プラス天井 $\displaystyle {\frac {RL}{2}}}$ これは、以上で最小の整数です。 $\displaystyle {\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 while L != R do m := L + ceil((R - L) / 2) A[m] > Tの場合、 R := m − 1 それ以外の場合： L := m A[L] = Tの場合、 L を返す。失敗を返す。

重複する要素

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

最も左の要素を見つける手順

最も左の要素を見つけるには、次の手順を使用できます。^{[ 10 ]}

セット $L$ に $0$ そして $R$ に $n$ 。
その間 $L<R$ $L<R$ 、
1. セット $m$ （中央要素の位置） $L$ プラス床 $\displaystyle {\frac {RL}{2}}}$ これは、以下の最大の整数です。 $\displaystyle {\frac {RL}{2}}}$ 。
2. もし $A_{m}<T$ 、セット $L$ に $m+1$ 。
3. それ以外、 $A_{m}\geq T$ ; セット $R$ に $m$ 。
戻る $L$ 。

もし $L<n$ そして $A_{L}=T$ 、それから $A_{L}$ は、 $T$ 。たとえ $T$ 配列に含まれていません。 $L$ ランクは $T$ 配列内、または配列内の以下の値より小さい要素の数 $T$ 。

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

関数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$ $L<R$ 、
1. セット $m$ （中央要素の位置） $L$ プラス床 $\displaystyle {\frac {RL}{2}}}$ これは、以下の最大の整数です。 $\displaystyle {\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$ 。

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

関数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を返す

近似一致

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

上記の手順では、対象値の位置を見つける完全一致のみを実行します。しかし、バイナリサーチはソートされた配列に対して動作するため、バイナリサーチを拡張して近似一致を実行することは容易です。たとえば、バイナリサーチを使用して、特定の値に対して、そのランク（より小さい要素の数）、先行要素（次に小さい要素）、後続要素（次に大きい要素）、および最近傍を計算できます。2つの値の間の要素の数を求める範囲クエリは、2 つのランククエリで実行できます。 ^{[ 11 ]}

最左端の要素を見つける手順でランククエリを実行できます。この手順は、目標値より小さい要素の数を返します。 ^{[ 11 ]}
先行クエリはランククエリで実行できます。ターゲット値のランクが $r$ その前身は $r-1$ [ ¹²^]
後続クエリの場合、最も右の要素を見つける手順を使用できます。ターゲット値に対して手順を実行した結果が $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 }$ 表記法は、引数以下の最大の整数を返す床関数を表し、 $\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 }$ 反復回数は、ツリーの2番目に深いレベルで探索が終了する場合、最悪の場合より1回少ない。^{[ 15 ]}

平均的に、各要素が検索される確率が等しいと仮定すると、二分探索では $\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)$ 平均反復回数は、要素間と要素外の範囲が検索される可能性が等しいと仮定した場合である。^{[ 14 ]}

最良の場合、ターゲット値が配列の中央の要素である場合、1回の反復でその位置が返されます。^{[ 16 ]}

反復回数に関して言えば、要素の比較のみで動作する検索アルゴリズムは、平均および最悪の場合のパフォーマンスにおいて、二分探索よりも優れているものはありません。二分探索を表す比較木は、木の最下位レベルより上のすべてのレベルが完全に満たされているため、可能な限り少ないレベルを持ちます。^{[ b ]}そうでなければ、検索アルゴリズムは反復で少数の要素しか削除できず、平均および最悪の場合に必要な反復回数が増加します。これは、比較に基づく他の検索アルゴリズムの場合にも当てはまります。これらのアルゴリズムは、一部のターゲット値ではより高速に動作するかもしれませんが、すべての要素の平均パフォーマンスは二分探索よりも劣ります。配列を半分に分割することで、二分探索は両方の部分配列のサイズが可能な限り類似するようにします。^{[ 14 ]}

空間の複雑さ

バイナリサーチでは、配列のサイズに関係なく、配列インデックスまたはメモリ位置へのポインタである要素へのポインタが 3 つ必要になります。したがって、バイナリサーチの空間計算量は次のようになります。 $O(1)$ RAM モデルの計算という言葉で。

平均ケースの導出

二分探索で実行される平均反復回数は、各要素が検索される確率に依存します。平均的なケースは、検索が成功した場合と失敗した場合で異なります。検索が成功した場合は、各要素が検索される確率は等しいと仮定します。検索が失敗した場合は、要素間および要素外の区間が検索される確率は等しいと仮定します。検索が成功した場合の平均ケースは、すべての要素をちょうど1回検索するために必要な反復回数を、で割った値です。 $n$ 、要素の数。検索が失敗する平均的なケースは、各区間内で要素をちょうど 1 回検索するために必要な反復回数をで割ったものです。 $n+1$ 間隔。^{[ 14 ]}

検索結果

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

$二分探索は比較による探索に最適なアルゴリズムであるため、この問題は、 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$

平均反復回数は $1+{\frac {10}{7}}=2{\frac {3}{7}}$ 平均ケースの式に基づく。合計は $I(n)$ 以下のように簡略化できます。^{[ 14 ]}

$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)$ : ^{[ 14 ]}

$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つの子を持つように、外部ノードと呼ばれる追加の子ノードが追加されます。このようにすることで、検索が失敗した場合は、最後の反復処理で残った単一の要素を親とする外部ノードへのパスとして表現できます。外部パスとは、ルートから外部ノードへのパスです。外部パスの長さは、すべての固有の外部パスの長さの合計です。 $n$ 要素は正の整数であり、外部パスの長さは $E(n)$ すると、検索が失敗した場合の平均反復回数は $T'(n)={\frac {E(n)}{n+1}}$ 、最初の反復をカウントするために1回の反復が追加されます。外部パスの長さは、 $n+1$ の代わりに $n$ なぜなら $n+1$ 外部パスは、配列の要素間および要素の外側の間隔を表します。^{[ 14 ]}

この問題は同様に、すべての二分木の最小外部パス長を決定することに帰着します。 $n$ ノード。すべての二分木において、外部パスの長さは内部パスの長さに等しい。 $2n$ [ ¹⁷^]式を代入する^と $I(n)$ : ^{[ 14 ]}

$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)$ 検索が失敗した場合の平均ケースは次のように決定できます。^{[ 14 ]}

$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回の反復が追加されます。比較ループは1回しか実行されないため、 ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ 最悪の場合、反復ごとの効率のわずかな向上は、非常に大きな場合を除いて、追加の反復を補うことはできません。 ${\textstyle n}$ [ ^c^]^[¹⁸^]^[¹⁹^]

その他の考慮事項

比較コスト

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

浮動小数点の高速比較は、整数として比較することで可能です。ただし、この種の比較は全順序を形成するため、すべての浮動小数点値は互いに異なり、自身と同じになります。これは、-0.0 が 0.0 と同じであるべきで、NaN が自身を含む他のどの値とも同じように比較されないべきである典型的な比較とは異なります。^{[ 20 ]}^{[ 21 ]}

分岐予測

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

キャッシュの使用状況

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

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

二分探索と他の方式との比較

挿入と削除操作が検索と交互に行われる場合、バイナリサーチを使用したソート済み配列は非常に非効率的なソリューションであり、 ${\textstyle O(n)}$ このような操作ごとに時間がかかります。さらに、ソートされた配列は、特に要素が頻繁に配列に挿入される場合、メモリの使用を複雑にする可能性があります。^{[ 25 ]}挿入と削除をはるかに効率的にサポートする他のデータ構造があります。バイナリサーチは、完全一致とセットメンバーシップ（ターゲット値が値のコレクションに含まれているかどうかの判定）を実行するために使用できます。より高速な完全一致とセットメンバーシップをサポートするデータ構造があります。ただし、他の多くの検索方式とは異なり、バイナリサーチは効率的な近似一致に使用でき、通常はこのような一致を ${\textstyle O(\log n)}$ 値自体の型や構造に関係なく、時間もかかりません。^{[ 26 ]}さらに、最小要素や最大要素を見つけるなど、ソートされた配列に対して効率的に実行できる操作もあります。^{[ 11 ]}

線形探索

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

木々

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

しかし、バイナリサーチは通常、検索においてより効率的です。バイナリサーチツリーは不完全にバランスが取れていない可能性が高く、バイナリサーチよりもわずかにパフォーマンスが劣ります。これは、自身のノードのバランスが取れているバランスの取れたバイナリサーチツリーにも当てはまります。なぜなら、バランスの取れたバイナリサーチツリーは、可能な限り少ないレベルのツリーを生成することはほとんどないからです。バランスの取れたバイナリサーチツリーを除いて、ツリーは、2 つの子を持つ内部ノードが少ないほど著しく不均衡になる可能性があり、その結果、平均および最悪の場合の検索時間が近づきます。 ${\textstyle n}$ 比較。^{[ e ]}二分探索木はソート済み配列よりも多くのスペースを必要とします。^{[ 33 ]}

バイナリサーチツリーは、ハードディスクに格納された外部メモリでの高速検索に適しています。バイナリサーチツリーはファイルシステム内で効率的に構造化できるためです。Bツリーはこのツリー構成方法を一般化したものです。Bツリーは、データベースやファイルシステムなどの長期ストレージを整理するためによく使用されます。^{[ 34 ]}^{[ 35 ]}

ハッシュ化

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

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

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

近似的な結果を得るには、ハッシュに基づく別の確率的データ構造であるブルームフィルタを使用します。ブルームフィルタは、ビット配列と複数のハッシュ関数を使用してキーをエンコードすることで、キーのセットを格納します。ブルームフィルタは、ほとんどの場合、ビット配列よりもはるかにスペース効率が良く、速度もそれほど遅くありません。 ${\textstyle k}$ ハッシュ関数、メンバーシップクエリには ${\textstyle O(k)}$ 時間。しかし、ブルームフィルタは誤検出の問題を抱えています。^{[ g ]}^{[ h ]}^{[ 43 ]}

その他のデータ構造

ソート済み配列の検索やその他の操作において、場合によってはバイナリサーチよりも優れたデータ構造が存在する。たとえば、検索、近似一致、およびソート済み配列で利用可能な操作は、van Emde Boas ツリー、融合ツリー、トライ、ビット配列などの特殊なデータ構造上でバイナリサーチよりも効率的に実行できる。これらの特殊なデータ構造が高速なのは、特定の属性を持つキー (通常は小さな整数であるキー) の特性を利用するためであり、その属性を持たないキーの場合は時間またはスペースを消費する。^{[ 26 ]}キーが順序付け可能であれば、これらの操作はキーの種類に関係なく、ソート済み配列上で常に少なくとも効率的に実行できる。Judy 配列などの一部の構造は、効率性と近似一致を実行する能力を維持しながら、この問題を軽減するために複数のアプローチを組み合わせて使用する。^{[ 41 ]}

バリエーション

均一二分探索

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

指数探索

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

補間検索

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

一般的な補間関数は線形補間です。 $A$ 配列です。 $L,R$ はそれぞれ下限値と上限値であり、 $T$ がターゲットである場合、ターゲットは約 $(T-A_{L})/(A_{R}-A_{L})$ その間の $L$ そして $R$ 線形補間を使用し、配列要素の分布が均一またはほぼ均一である場合、補間探索は ${\textstyle O(\log \log n)}$ 比較。^{[ 47 ]}^{[ 48 ]}^{[ 49 ]}

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

分数カスケード

分数カスケードは、複数のソート済み配列で同じ要素をバイナリ検索する速度を向上させる手法です。各配列を個別に検索するには、 ${\textstyle O(k\log n)}$ 時間、 ${\textstyle k}$ は配列の数です。分数カスケードにより、これはに減少します。 ${\textstyle O(k+\log n)}$ 各配列に各要素と他の配列内での位置に関する特定の情報を格納することによって。^{[ 50 ]}^{[ 51 ]}

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

グラフへの一般化

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

ノイズのある二分探索

ノイズバイナリサーチアルゴリズムは、アルゴリズムが配列の要素を確実に比較できない場合に対処します。各要素ペアについて、アルゴリズムが誤った比較を行う一定の確率が存在します。ノイズバイナリサーチは、得られた位置の信頼性を制御する特定の確率で、ターゲットの正しい位置を見つけることができます。すべてのノイズバイナリサーチ手順は、少なくとも $(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$ は、手順が間違った位置をもたらす確率です。^{[ 53 ]}^{[ 54 ]}^{[ 55 ]}ノイズのある二分探索問題は、回答が間違っている可能性がある20の質問の変種であるレニー・ウラムゲーム[56]の^ケースとして考えることができ^ます^。^[⁵⁷^]

量子バイナリーサーチ

古典的なコンピュータは、最悪の場合、正確に ${\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 }$ は自然対数です。^{[ 58 ]}正確な量子バイナリーサーチ手順があり、 ${\textstyle 4\log _{605}n\approx 0.433\log _{2}n}$ 最悪の場合のクエリ数。^{[ 59 ]}それに対し、グローバーのアルゴリズムは、要素の順序付けされていないリストを検索するための最適な量子アルゴリズムであり、 $O({\sqrt {n}})$ クエリ。^{[ 60 ]}

歴史

項目のリストを並べ替えて検索を速くするというアイデアは古代に遡ります。最も古い既知の例は、紀元前200年頃にバビロンで発見されたイナキビト・アヌの粘土板です。この粘土板には、約500の六十進数とその逆数が辞書順に並べられており、特定の項目の検索が容易になっています。さらに、エーゲ海の島々では、最初の文字で並べられた名前のリストがいくつか発見されています。 1286年に完成したラテン語辞書であるカトリコンは、単語を最初の数文字ではなくアルファベット順に並べる規則を記述した最初の作品です。^{[ 9 ]}

1946 年、ジョン・モークリーは、コンピューティングの基礎となる大学の講義であるムーア・スクール講義の一部として、バイナリサーチについて初めて言及しました。 ^{[ 9 ]} 1957 年、ウィリアム・ウェズリー・ピーターソンは、補間サーチの最初の方法を発表しました。^{[ 9 ]}^{[ 61 ]} 1960 年、デリック・ヘンリー・レーマーがすべての配列で動作するバイナリサーチアルゴリズムを発表するまで、発表されたバイナリサーチアルゴリズムはすべて、長さが 2 のべき乗より 1 少ない配列に対してのみ機能しました。^{[ i ]}^[⁶³^] 1962 年、ヘルマン・ボッテンブルッフは、等価性の比較を最後に配置したバイナリサーチのALGOL 60実装を発表しました。これにより、平均反復回数は 1 回増加しましたが、反復ごとの比較回数は 1 回に減少しました。^[⁸^]一様二分探索は、 1971 年にスタンフォード大学の AK Chandra によって開発されました。^[⁹^] 1986 年に、Bernard ChazelleとLeonidas J. Guibas は、計算幾何学における多数の探索問題を解決する方法として分数カスケードを導入しました。^[⁵⁰^]^[⁶⁴^]^[⁶⁵^]

実装上の問題点

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

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

ジョン・ベントレーがプログラマー向けのコースで二分探索を問題として出題したところ、数時間かけても90%の学生が正しい解答を提供できなかったことがわかった。主な理由は、誤った実装では実行できなかったり、まれなエッジケースで間違った答えを返したりしたためである。^{[ 66 ]} 1988年に発表された調査によると、正確なコードは20冊の教科書のうち5冊にしか見当たらない。^{[ 67 ]}さらに、ベントレー自身が1986年に出版した著書『Programming Pearls』に掲載された二分探索の実装には、20年以上も検出されなかったオーバーフローエラーが含まれていた。Javaプログラミング言語ライブラリの二分探索の実装にも、9年以上同じオーバーフローバグが存在していた。^{[ 68 ]}

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

ループの終了条件が正しく定義されていない場合、無限ループが発生する可能性があります。 $L$ を超える $R$ 検索が失敗した場合は、その失敗を通知する必要があります。さらに、目的の要素が見つかったらループを終了するか、このチェックを最後に移動した実装の場合は、最後に検索が成功したか失敗したかのチェックを行う必要があります。ベントレーは、バイナリサーチを誤って実装したプログラマーのほとんどが、終了条件の定義に誤りがあったことを発見しました。^{[ 8 ]}^{[ 70 ]}

図書館サポート

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

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

注記

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

引用文献

↑ Williams, Jr., Louis F. (1976年4月22日).半区間探索（二分探索）法の改良. 第14回ACM南東部会議議事録. ACM. pp. 95–101 . doi : 10.1145/503561.503582 . 2017年3月12日のオリジナルからアーカイブ済み. 2018年6月29日取得.
1 2 Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「二分探索」。
↑バターフィールド＆ンゴンディ 2016、p. 46.
↑コーメンら。 2009 年、p. 39.
↑ Weisstein, Eric W. 「バイナリサーチ」 . MathWorld .
1 2 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 .
1 2 3 Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「アルゴリズム B」。
1 2 3 4 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 . 手順については、214ページ（§43）の「二分探索プログラム」というタイトルの項で説明されています。
1 2 3 4 5 6 Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「履歴と参考文献」。
1 2笠原・森下、2006 年、8-9 ページ。
1 2 3 Sedgewick & Wayne 2011、§3.1、「ランクと選抜」の項。
1 2 3 Goldman & Goldman 2008、pp. 461–463。
↑ Sedgewick & Wayne 2011、§3.1、「範囲クエリ」の項。
1 2 3 4 5 6 7 8 9 10 11 12 Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「二分探索のさらなる分析」。
↑ Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、定理B。
↑ Chang 2003、p. 169。
1 2 3 Knuth 1997、§2.3.4.5（「パスの長さ」）。
1 2 Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「演習23」。
↑ Rolfe, Timothy J. (1997). "二分探索における比較の解析的導出" . ACM SIGNUM Newsletter . 32 (4): 15– 19. doi : 10.1145/289251.289255 . S2CID 23752485 .
↑ Herf, Michael (2001 年 12 月). "radix tricks" . stereopsis: graphics .
↑ "f32、f64 用の total_cmp を実装 (golddranks による) · プルリクエスト #72568 · rust-lang/rust" . GitHub .– IEEE 754-2008および-2019からの関連引用が含まれています。型ダジャレの実装と説明が含まれています。
↑ 「二分探索は分岐予測の誤りを*排除*する - 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: some Lisp」 . pvk.ca .
↑ Knuth 1997、§2.2.2（「逐次割り当て」）。
1 2 3 4 Beame, Paul; Fich, Faith E. (2001). "Optimal bounds for the predecessor problem and related problems" . 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（「アプリケーション」）、「どのシンボルテーブル実装を使用すべきか？」。
↑クヌース 1998、§5.4.9（「ディスクとドラム」）。
↑ Knuth 1998、§6.2.4（「多分岐木」）。
↑クヌース 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（「ビット演算のコツとテクニック」）。
1 2 Silverstein, Alan、「Judy IV ショップマニュアル(PDF)」、Hewlett-Packard、pp. 80–81、2022年10月9日にオリジナルからアーカイブ(PDF)
1 2 Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Cuckoo filter: practically better than Bloom . Proceedings of the 10th ACM International 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、p.33 。
1 2 3 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 .
1 2 3 Chazelle, Bernard ; Liu, Ding (2001年7月6日).高次元における交差探索と分数カスケードの下限. 第33回ACM理論計算機科学シンポジウム. ACM. pp. 322–329 . doi : 10.1145/380752.380818 . ISBN 978-1-58113-349-32018年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 .
↑ Ben-Or, Michael; Hassidim, Avinatan (2008). "The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)" (PDF) . 49th Symposium on Foundations of Computer Science . pp. 221–230 . doi : 10.1109/FOCS.2008.58 . ISBN 978-0-7695-3436-72022年10月9日にオリジナルからアーカイブ（PDF）。
↑ Pelc, Andrzej (1989). "既知のエラー確率による探索" . Theoretical Computer Science . 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。
↑ Pelc, Andrzej (2002). "エラーのあるゲームの探索 ― 嘘つきへの対処の50年" . Theoretical Computer Science . 270 ( 1– 2): 71– 109. doi : 10.1016/S0304-3975(01)00303-6 .
↑アルフレッド・レンイ（1961年）。「情報理論の問題について」。マジャル語トゥドマニョスアカデミアマテマティカイクタトインテゼテネクコズレメニエイ。6 : 515–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理論計算機科学シンポジウム。フィラデルフィア、ペンシルベニア州。pp. 212–219。arXiv : quant-ph/9605043。doi : 10.1145/237814.237866。
↑ Peterson, William Wesley (1957). "ランダムアクセスストレージのアドレス指定". IBM Journal of Research and Development . 1 (2): 130– 146. doi : 10.1147/rd.12.0130 .
↑ "2ⁿ − 1". OEIS A000225 2016年6月8日にWayback Machineにアーカイブされました。2016年5月7日に取得。
↑レーマー、デリック (1960)「コンピュータに組み合わせのコツを教える」組み合わせ解析。応用数学シンポジウム論文集、第10巻、 180–181頁。doi : 10.1090 /psapm/010/ 0113289。ISBN 9780821813102. MR 0113289 . {{cite book}}ISBN /日付の不一致（ヘルプ）
↑ Chazelle, Bernard ; Guibas, Leonidas J. (1986). "Fractional cascading: I. A data structuring technique" (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), "Fractional cascading: II. Applications" (PDF) , Algorithmica , 1 ( 1– 4): 163– 191, doi : 10.1007/BF01840441 , S2CID 11232235
↑ベントレー 2000、§4.1（「二分探索の課題」）。
↑パティス、リチャード E. (1988). 「二分探索における教科書の誤り」。SIGCSE Bulletin . 20 : 190–194 . doi : 10.1145/52965.53012 .
↑ Bloch, Joshua (2006年6月2日). 「特報！すべて読んでください：ほぼすべての二分探索とマージソートは壊れています」 . Google Research Blog . 2016年4月1日のオリジナルからアーカイブ済み。 2016年4月21日取得。
↑ Ruggieri, Salvatore (2003). "On computing the semi-sum of two integers" (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日取得.
↑ベントレー 2000、§4.4（「原則」）。
↑ 「bsearch – ソート済みテーブルの二分探索」。The Open Group Base Specifications (第 7版)。The Open Group。2013年。2016年 3 月 21 日時点のオリジナルからアーカイブ済み。2016年3 月 28 日取得。
↑ストロストルップ 2013、p. 945。
↑ "std.range - D プログラミング言語" . dlang.org . 2020 年4 月 29 日取得.
↑ Unisys (2012)、COBOL ANSI-85 プログラミングリファレンスマニュアル、第 1 巻、 598～ 601ページ
↑ 「パッケージのソート」。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 ソフトウェア財団。2018年 3 月 25 日のオリジナルからアーカイブ済み。2018年3 月 26 日取得。
↑フィッツジェラルド 2015、p. 152。
↑ 「プリミティブ型」。Rust標準ライブラリ。Rust財団。2024年。 2024年5月25日取得。slice

情報源

ベントレー、ジョン（ 2000）。プログラミングの真珠（第2 版）。アディソン・ウェスリー。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）。ルビーポケットリファレンス。カリフォルニア州セバストポル：オライリーメディア。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。
モファット、アリスター；ターピン、アンドリュー（2002）。圧縮と符号化アルゴリズム。ドイツ、ハンブルク：クルーワー・アカデミック・パブリッシャーズ。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。

外部リンク

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

[6] $O$ はビッグオー記法であり、 $\log$ は対数です。ビッグオー記法では、与えられた底のすべての対数は別の底の別の対数の定数倍であるため、対数の底は関係ありません。つまり、 $\log _{b}(n)=\log _{k}(n)\div \log _{k}(b)$ 、どこ $\log _{k}(b)$ 定数です。

[18] 比較のみに基づく検索アルゴリズムは、二分比較木を使用して表現できます。内部パスとは、ルートから既存のノードへの任意のパスのことです。 $I$ を内部パスの長さ、つまりすべての内部パスの長さの合計とします。各要素が検索される確率が等しい場合、平均的なケースは $1+{\frac {I}{n}}$ または、単純にツリーのすべての内部パスの長さの平均に1を加えた値です。これは、内部パスが検索アルゴリズムがターゲットと比較する要素を表しているためです。これらの内部パスの長さは、ルートノード後の反復回数を表します。これらの長さの平均をルートでの1回の反復に加えると、平均的なケースが得られます。したがって、比較の平均回数を最小化するには、内部パスの長さを $I$ 最小化する必要がある。二分探索用の木は内部パス長を最小化することがわかっている。Knuth 1998 は、外部パス長 (既に存在する各ノードに対して両方の子が存在するすべてのノードにわたるパス長) は、外部ノード (子を持たないノード) が木の 2 つの連続したレベル内にある場合に最小化されることを証明した。これは内部パスにも適用され、内部パス長は $I$ 外部経路の長さに線形関係がある $E$ 任意の木の場合 $n$ ノード、 $I=E-2n$ 各サブツリーのノード数がほぼ同じ場合、または配列が各反復で半分に分割される場合、外部ノードとその内部親ノードは2つのレベル内に収まります。したがって、バイナリサーチは比較ツリーの内部パス長が最小となるため、平均比較回数を最小化します。^{[ 14 ]}

[21] クヌース 1998 は、通常のコンピュータを表現するためにクヌースが設計した MIXコンピュータモデル上で、このバリエーションで検索が成功した場合の平均実行時間が次のようになること ${\textstyle 17.5\log _{2}n+17}$ 時間の単位を比較すると ${\textstyle 18\log _{2}n-16}$ 通常の二分探索の単位。このバリエーションの時間計算量はわずかに緩やかに増加するが、初期計算量が高くなるという代償がある。^{[ 18 ]}

[31] クヌースは1998年に、これら2つの検索アルゴリズムの正式な時間性能分析を行った。クヌースが通常のコンピュータの模範として設計したクヌースのMIXコンピュータでは、二分探索は平均して ${\textstyle 18\log n-16}$ 成功する検索には単位時間かかるのに対し、リストの最後に番兵ノードがある線形検索では ${\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}}$ 単位。線形探索は最小限の計算しか必要としないため、初期の複雑さは低いが、複雑さはすぐに二分探索を上回る。MIX コンピュータでは、番兵付き線形探索よりも二分探索が優れているのは、次の条件を満たす場合のみである。 ${\textstyle n>44}$ [ ¹⁴^]^[²⁷^]

[37] 値をソート順または最小値と最大値を交互に並べたキーパターンで挿入すると、平均および最悪の場合の検索時間を最大化する二分探索木が生成されます。^{[ 32 ]}

[43] 一部のハッシュテーブル実装では、定数時間での検索が保証されている。^{[ 37 ]}

[49] これは、特定のキーに対してハッシュ関数が指すすべてのビットを設定するだけで、1つ以上の関数で共通のハッシュ位置を持つ他のキーのクエリに影響を与える可能性があるためです。^{[ 42 ]}

[50] ブルームフィルタには、その複雑さを改善したり、削除をサポートしたりする改良版が存在する。例えば、カッコウフィルタはカッコウハッシュを利用してこれらの利点を得ている。^{[ 42 ]}

[71] つまり、長さ 1、3、7、15、31 ... の配列^{[ 62 ]}

[Williams1976-1] Williams, Jr., Louis F. (1976年4月22日).半区間探索（二分探索）法の改良. 第14回ACM南東部会議議事録. ACM. pp. 95–101 . doi : 10.1145/503561.503582 . 2017年3月12日のオリジナルからアーカイブ済み. 2018年6月29日取得.

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Binary_search"-2] 1 2 Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「二分探索」。

[FOOTNOTEButterfieldNgondi201646-3] バターフィールド＆ンゴンディ 2016、p. 46.

[FOOTNOTECormenLeisersonRivestStein200939-4] コーメンら。 2009 年、p. 39.

[5] Weisstein, Eric W. 「バイナリサーチ」 . MathWorld .

[FloresMadpis1971-7] 1 2 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 .

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Algorithm_B"-8] 1 2 3 Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「アルゴリズム B」。

[Bottenbruch1962-9] 1 2 3 4 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 . 手順については、214ページ（§43）の「二分探索プログラム」というタイトルの項で説明されています。

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"History_and_bibliography"-10] 1 2 3 4 5 6 Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「履歴と参考文献」。

[FOOTNOTEKasaharaMorishita20068–9-11] 1 2笠原・森下、2006 年、8-9 ページ。

[FOOTNOTESedgewickWayne2011§3.1,_subsection_"Rank_and_selection"-12] 1 2 3 Sedgewick & Wayne 2011、§3.1、「ランクと選抜」の項。

[FOOTNOTEGoldmanGoldman2008461–463-13] 1 2 3 Goldman & Goldman 2008、pp. 461–463。

[FOOTNOTESedgewickWayne2011§3.1,_subsection_"Range_queries"-14] Sedgewick & Wayne 2011、§3.1、「範囲クエリ」の項。

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Further_analysis_of_binary_search"-15] 1 2 3 4 5 6 7 8 9 10 11 12 Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「二分探索のさらなる分析」。

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_"Theorem_B"-16] Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、定理B。

[FOOTNOTEChang2003169-17] Chang 2003、p. 169。

[FOOTNOTEKnuth1997§2.3.4.5_("Path_length")-19] 1 2 3 Knuth 1997、§2.3.4.5（「パスの長さ」）。

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Exercise_23"-20] 1 2 Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「演習23」。

[22] Rolfe, Timothy J. (1997). "二分探索における比較の解析的導出" . ACM SIGNUM Newsletter . 32 (4): 15– 19. doi : 10.1145/289251.289255 . S2CID 23752485 .

[Herf_2001-23] Herf, Michael (2001 年 12 月). "radix tricks" . stereopsis: graphics .

[rust_total_cmp-24] "f32、f64 用の total_cmp を実装 (golddranks による) · プルリクエスト #72568 · rust-lang/rust" . GitHub .– IEEE 754-2008および-2019からの関連引用が含まれています。型ダジャレの実装と説明が含まれています。

[25] 「二分探索は分岐予測の誤りを*排除*する - Paul Khuong: some Lisp」. pvk.ca.

[26] Khuong, Paul-Virak; Morin, Pat (2017). "比較に基づく検索のための配列レイアウト". Journal of Experimental Algorithmics . 22. Article 1.3. arXiv : 1509.05053 . doi : 10.1145/3053370 . S2CID 23752485 .

[27] 「バイナリサーチはキャッシュの病理的なケースです - Paul Khuong: some Lisp」 . pvk.ca .

[FOOTNOTEKnuth1997§2.2.2_("Sequential_Allocation")-28] Knuth 1997、§2.2.2（「逐次割り当て」）。

[pred-29] 1 2 3 4 Beame, Paul; Fich, Faith E. (2001). "Optimal bounds for the predecessor problem and related problems" . Journal of Computer and System Sciences . 65 (1): 38–72 . doi : 10.1006/jcss.2002.1822 .

[FOOTNOTEKnuth1998Answers_to_Exercises_(§6.2.1)_for_"Exercise_5"-30] Knuth 1998、「練習問題5」の解答（§6.2.1）。

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table")-32] Knuth 1998、§6.2.1（「順序付きテーブルの検索」）。

[FOOTNOTEKnuth1998§5.3.1_("Minimum-Comparison_sorting")-33] Knuth 1998、§5.3.1（「最小比較ソート」）。

[FOOTNOTESedgewickWayne2011§3.2_("Ordered_symbol_tables")-34] Sedgewick & Wayne 2011、§3.2（「順序付きシンボルテーブル」）。

[FOOTNOTESedgewickWayne2011§3.2_("Binary_Search_Trees"),_subsection_"Order-based_methods_and_deletion"-35] Sedgewick & Wayne 2011、§3.2（「二分探索木」）、サブセクション「順序ベースの方法と削除」。

[FOOTNOTEKnuth1998§6.2.2_("Binary_tree_searching"),_subsection_"But_what_about_the_worst_case?"-36] Knuth 1998、§6.2.2（「二分木探索」）、サブセクション「最悪の場合はどうなるのか？」。

[FOOTNOTESedgewickWayne2011§3.5_("Applications"),_"Which_symbol-table_implementation_should_I_use?"-38] Sedgewick & Wayne 2011、§3.5（「アプリケーション」）、「どのシンボルテーブル実装を使用すべきか？」。

[FOOTNOTEKnuth1998§5.4.9_("Disks_and_Drums")-39] クヌース 1998、§5.4.9（「ディスクとドラム」）。

[FOOTNOTEKnuth1998§6.2.4_("Multiway_trees")-40] Knuth 1998、§6.2.4（「多分岐木」）。

[FOOTNOTEKnuth1998§6.4_("Hashing")-41] クヌース 1998、§6.4（「ハッシュ化」）。

[FOOTNOTEKnuth1998§6.4_("Hashing"),_subsection_"History"-42] Knuth 1998、§6.4（「ハッシュ化」）、サブセクション「歴史」。

[44] ディーツフェルビンガー、マーティン;アンナ・カーリン;クルト州;マイヤー・アウフ・デア・ハイデ、フリードヘルム。ローナート、ハンス。タージャン、ロバート E. (1994 年 8 月)。「動的完全ハッシュ: 上限と下限」。SIAM ジャーナルオンコンピューティング。23 (4): 738–761。土井: 10.1137/S0097539791194094。

[45] Morin, Pat. "ハッシュテーブル" (PDF) . p. 1. 2022年10月9日にオリジナルからアーカイブ(PDF) 。 2016年3月28日に取得。

[FOOTNOTEKnuth2011§7.1.3_("Bitwise_Tricks_and_Techniques")-46] Knuth 2011、§7.1.3（「ビット演算のコツとテクニック」）。

[judyarray-47] 1 2 Silverstein, Alan、「Judy IV ショップマニュアル(PDF)」、Hewlett-Packard、pp. 80–81、2022年10月9日にオリジナルからアーカイブ(PDF)

[cuckoofilter-48] 1 2 Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Cuckoo filter: practically better than Bloom . Proceedings of the 10th ACM International Conference on Emerging Networking Experiments and Technologies. pp. 75–88 . doi : 10.1145/2674005.2674994 .

[51] 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 .

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"An_important_variation"-52] Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「重要なバリエーション」。

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Algorithm_U"-53] Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「アルゴリズム U」。

[FOOTNOTEMoffatTurpin200233-54] モファット＆ターピン 2002、p.33 。

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Interpolation_search"-55] 1 2 3 Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「補間検索」。

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Exercise_22"-56] Knuth 1998、§6.2.1（「順序付きテーブルの検索」）、サブセクション「演習22」。

[57] 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 .

[ChazelleLiu2001-58] 1 2 3 Chazelle, Bernard ; Liu, Ding (2001年7月6日).高次元における交差探索と分数カスケードの下限. 第33回ACM理論計算機科学シンポジウム. ACM. pp. 322–329 . doi : 10.1145/380752.380818 . ISBN 978-1-58113-349-32018年6月30日に取得。

[ChazelleLiu2004-59] 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 日取得.

[60] Emamjomeh-Zadeh, Ehsan; Kempe, David; Singhal, Vikrant (2016).グラフにおける決定論的および確率的二分探索. 第 48 回ACM 理論計算機科学シンポジウム. pp. 519–532 . arXiv : 1503.00805 . doi : 10.1145/2897518.2897656 .

[61] Ben-Or, Michael; Hassidim, Avinatan (2008). "The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)" (PDF) . 49th Symposium on Foundations of Computer Science . pp. 221–230 . doi : 10.1109/FOCS.2008.58 . ISBN 978-0-7695-3436-72022年10月9日にオリジナルからアーカイブ（PDF）。

[pelc1989-62] Pelc, Andrzej (1989). "既知のエラー確率による探索" . Theoretical Computer Science . 63 (2): 185– 202. doi : 10.1016/0304-3975(89)90077-7 .

[63] Rivest, Ronald L. ; Meyer, Albert R. ; Kleitman, Daniel J. ; Winklmann, K.二分探索手順におけるエラーへの対処。第 10 回ACM 理論計算機科学シンポジウム。doi : 10.1145/800133.804351。

[64] Pelc, Andrzej (2002). "エラーのあるゲームの探索 ― 嘘つきへの対処の50年" . Theoretical Computer Science . 270 ( 1– 2): 71– 109. doi : 10.1016/S0304-3975(01)00303-6 .

[65] アルフレッド・レンイ（1961年）。「情報理論の問題について」。マジャル語トゥドマニョスアカデミアマテマティカイクタトインテゼテネクコズレメニエイ。6 : 515–516。MR 0143666。

[66] 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 .

[quantumalgo-67] 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 .

[68] Grover, Lov K. ( 1996 ) .データベース検索のための高速量子力学的アルゴリズム。第28回ACM理論計算機科学シンポジウム。フィラデルフィア、ペンシルベニア州。pp. 212–219。arXiv : quant-ph/9605043。doi : 10.1145/237814.237866。

[69] Peterson, William Wesley (1957). "ランダムアクセスストレージのアドレス指定". IBM Journal of Research and Development . 1 (2): 130– 146. doi : 10.1147/rd.12.0130 .

[70] "2ⁿ − 1". OEIS A000225 2016年6月8日にWayback Machineにアーカイブされました。2016年5月7日に取得。

[72] レーマー、デリック (1960)「コンピュータに組み合わせのコツを教える」組み合わせ解析。応用数学シンポジウム論文集、第10巻、 180–181頁。doi : 10.1090 /psapm/010/ 0113289。ISBN 9780821813102. MR 0113289 . {{cite book}}ISBN /日付の不一致（ヘルプ）

[73] Chazelle, Bernard ; Guibas, Leonidas J. (1986). "Fractional cascading: I. A data structuring technique" (PDF) . Algorithmica . 1 ( 1– 4): 133– 162. CiteSeerX 10.1.1.117.8349 . doi : 10.1007/BF01840440 . S2CID 12745042 .

[74] Chazelle, Bernard ; Guibas, Leonidas J. (1986), "Fractional cascading: II. Applications" (PDF) , Algorithmica , 1 ( 1– 4): 163– 191, doi : 10.1007/BF01840441 , S2CID 11232235

[FOOTNOTEBentley2000§4.1_("The_Challenge_of_Binary_Search")-75] ベントレー 2000、§4.1（「二分探索の課題」）。

[textbook-76] パティス、リチャード E. (1988). 「二分探索における教科書の誤り」。SIGCSE Bulletin . 20 : 190–194 . doi : 10.1145/52965.53012 .

[77] Bloch, Joshua (2006年6月2日). 「特報！すべて読んでください：ほぼすべての二分探索とマージソートは壊れています」 . Google Research Blog . 2016年4月1日のオリジナルからアーカイブ済み。 2016年4月21日取得。

[semisum-78] Ruggieri, Salvatore (2003). "On computing the semi-sum of two integers" (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日取得.

[FOOTNOTEBentley2000§4.4_("Principles")-79] ベントレー 2000、§4.4（「原則」）。

[80] 「bsearch – ソート済みテーブルの二分探索」。The Open Group Base Specifications (第 7版)。The Open Group。2013年。2016年 3 月 21 日時点のオリジナルからアーカイブ済み。2016年3 月 28 日取得。

[FOOTNOTEStroustrup2013945-81] ストロストルップ 2013、p. 945。

[82] "std.range - D プログラミング言語" . dlang.org . 2020 年4 月 29 日取得.

[83] Unisys (2012)、COBOL ANSI-85 プログラミングリファレンスマニュアル、第 1 巻、 598～ 601ページ

[84] 「パッケージのソート」。Goプログラミング言語。2016年4月25日のオリジナルからアーカイブ済み。 2016年4月28日取得。

[85] "java.util.Arrays" . Java Platform Standard Edition 8 ドキュメント. Oracle Corporation . 2016 年 4 月 29 日にオリジナルからアーカイブ済み. 2016 年5 月 1 日に取得.

[86] "java.util.Collections" . Java Platform Standard Edition 8 ドキュメント. Oracle Corporation . 2016 年 4 月 23 日のオリジナルからアーカイブ済み. 2016 年5 月 1 日取得.

[87] "List<T>.BinarySearch メソッド (T)" . Microsoft Developer Network . 2016 年 5 月 7 日のオリジナルからアーカイブ済み. 2016 年4 月 10 日取得.

[88] "NSArray" . Mac Developer Library . Apple Inc. 2016年4月17日のオリジナルからアーカイブ済み。2016年5月1日に取得。

[89] "CFArray" . Mac Developer Library . Apple Inc. 2016年4月20日のオリジナルからアーカイブ済み。2016年5月1日に取得。

[90] "8.6. bisect — 配列の二分法アルゴリズム" . Python 標準ライブラリ. Python ソフトウェア財団。2018年 3 月 25 日のオリジナルからアーカイブ済み。2018年3 月 26 日取得。

[FOOTNOTEFitzgerald2015152-91] フィッツジェラルド 2015、p. 152。

[92] 「プリミティブ型」。Rust標準ライブラリ。Rust財団。2024年。 2024年5月25日取得。slice

[ 1 ]

[ 2 ]

[ 3 ]

[

[

[ a ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

12

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ b ]

[ 17 ]

c

[

[

[ 20 ]

[ 21 ]

[ 22 ]

[

[ 24 ]

[ 25 ]

[ 26 ]

[ d ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ e ]

[ 33 ]

[ 34 ]

[ 35 ]

[

[

[

[

[ 40 ]

[ 41 ]

[ g ]

[ h ]

[ 43 ]

[

[

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]

[ 55 ]

ケース

ます

[ 58 ]

[ 59 ]

[ 60 ]

[ 61 ]

[ i ]

[

[

[

[ 66 ]

[ 67 ]

[ 68 ]

69

[ 70 ]

[

[ 72 ]

[

[ 74 ]

[

[

[

[ 78 ]

[

[

[ 81 ]

[ 82 ]

[

[

[ 32 ]

[ 37 ]

[ 42 ]

[ 62 ]