二分探索

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

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

1. セット${\displaystyle L}$に${\displaystyle 0}$そして${\displaystyle R}$に${\displaystyle n-1}$。
2. その間${\displaystyle L\neq R}$、
   1. セット${\displaystyle m}$（中央要素の位置）${\displaystyle L}$プラス天井​$\displaystyle {\frac {RL}{2}}}$これは、以上で最小の整数です。$\displaystyle {\frac {RL}{2}}}$。
   2. もし${\displaystyle A_{m}>T}$、 セット${\displaystyle R}$に${\displaystyle m-1}$。
   3. それ以外、${\displaystyle A_{m}\leq T}$; セット${\displaystyle L}$に${\displaystyle m}$。
3. 今${\displaystyle L=R}$検索は完了しました。${\displaystyle A_{L}=T}$、 戻る${\displaystyle 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 を返す。失敗を返す。

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

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

もし${\displaystyle L<n}$そして${\displaystyle A_{L}=T}$、 それから${\displaystyle A_{L}}$は、${\displaystyle T}$。 たとえ${\displaystyle T}$配列に含まれていません。${\displaystyle L}$ランクは​${\displaystyle T}$配列内、または配列内の要素のうち、より小さいものの数${\displaystyle 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 ]}

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

もし${\displaystyle R>0}$そして${\displaystyle A_{R-1}=T}$、 それから${\displaystyle A_{R-1}}$は、${\displaystyle T}$。 たとえ${\displaystyle T}$配列に含まれていません。${\displaystyle nR}$は、配列内の要素のうち、より大きい数です。${\displaystyle 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を返す

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

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

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

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

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

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

$${\displaystyle 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}$$

式を代入すると${\displaystyle I(n)}$方程式に${\displaystyle T(n)}$: ^{[ 14 ]}

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

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

${\displaystyle 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}}$

式を代入すると${\displaystyle E(n)}$方程式に${\displaystyle T'(n)}$検索が失敗した場合の平均ケースは次のように決定できます。^{[ 14 ]}

${\displaystyle 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 ] [ 18 ] [ 19 ]​}

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

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

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

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

Paul Khuong has noted that binary search on large (≥ 512 KiB) arrays of exactly a power-of-two size tends to cause an additional problem with how CPU caches are implemented. Specifically, the translation lookaside buffer (TLB) is often implemented as a content-addressable memory (CAM), with the "key" usually being the lower bits of a requested address. When searching on an array of exactly a power-of-two size, memory address with the same lower bits tend to be accessed, causing collisions ("aliasing") with the "key" used to fetch the CAM. The typical TLB is 4-way associative, meaning it can handle at most four addresses hitting the same "key", after which TLB thrashing happens. (Although the other levels of CPU caches also use a similar setup, they manage smaller areas with a higher way count, usually 8 or 16, so they are less affected.) This can be prevented by offsetting the split point of the binary search so it divides at 31⁄64 instead of exactly the middle.^[24]