指数探索

コンピュータサイエンスにおいて、指数探索（倍増探索、ギャロッピング探索、またはStruzik探索とも呼ばれる）^[1]は、1976年にJon BentleyとAndrew Chi-Chih Yaoによって作成された、ソートされた無限リストを検索するアルゴリズムです。 ^[2]これを実装する方法は数多くありますが、最も一般的なのは、検索キーが存在する範囲を決定し、その範囲内でバイナリ検索を実行することです。これにはO (log  i )の時間がかかります。ここで、iは、検索キーがリスト内にある場合はリスト内の検索キーの位置、検索キーがリスト内にない場合は検索キーがあるべき位置です。

指数検索は、制限付きリストの検索にも使用できます。検索対象の要素が配列の先頭近くにある場合、指数検索は、制限付きリストのバイナリ検索などの従来の検索よりも優れたパフォーマンスを発揮します。これは、指数検索はO (log  i ) 時間で実行されるためです。ここで、iはリスト内の検索対象要素のインデックスです。一方、バイナリ検索はO (log  n ) 時間で実行されます。ここで、n はリスト内の要素数です。

指数検索では、指定された入力値 (検索「キー」) をソートされた無制限のリストで検索できます。アルゴリズムは 2 つの段階で構成されています。最初の段階では、リスト内に検索キーがある場合にキーが存在する範囲を決定します。2 番目の段階では、この範囲に対してバイナリ検索が実行されます。最初の段階では、リストが昇順でソートされていると仮定して、アルゴリズムは最初の指数jを探します。この場合、値 2 ^jは検索キーよりも大きくなります。この値 2 ^{j は}バイナリ検索の上限となり、前の 2 の累乗である 2 j ^{- 1}はバイナリ検索の下限となります。^[3]

// 長さsizeの配列arr内のkeyの位置を返します。
template < typename T > int exponential_search ( T arr [], int size , T key ) { if ( size == 0 ) { return NOT_FOUND ; }  
      

        
         
    

    int bound = 1 ; while ( bound < size && arr [ bound ] < key ) { bound *= 2 ; }   
            
          
    

    戻り値binary_search ( arr 、key 、bound / 2 、min ( bound 、size ) ) ; }     

各ステップで、アルゴリズムは検索キーの値と現在の検索インデックスのキーの値を比較します。現在のインデックスの要素が検索キーより小さい場合、アルゴリズムは繰り返し、次の検索インデックスにスキップしてそれを2倍し、次の2の累乗を計算します。^[3]現在のインデックスの要素が検索キーより大きい場合、アルゴリズムは、検索キーがリストに含まれている場合、前の検索インデックス 2 ^{j - 1}と現在の検索インデックス 2 ^jによって形成される間隔にあることを認識します。次に、バイナリ検索が実行され、検索キーがリストにない場合は失敗、またはリスト内の検索キーの位置のいずれかの結果が返されます。

アルゴリズムの最初のステージはO (log  i ) 時間がかかります。ここで、i はリスト内で検索キーが配置されるインデックスです。これは、バイナリ検索の上限を決定する際に、while ループが正確に回実行されるためです。リストはソートされているため、検索インデックスを 回倍増すると、アルゴリズムはi以上の検索インデックスに到達します。そのため、アルゴリズムの最初のステージはO (log  i ) 時間がかかります。 ${\displaystyle \lceil \log(i)\rceil }$${\displaystyle \lceil \log(i)\rceil }$${\displaystyle 2^{\lceil \log(i)\rceil }\geq i}$

アルゴリズムの 2 番目の部分もO (log  i ) 時間がかかります。2 番目のステージは単純なバイナリ検索なので、O (log  n ) かかります。ここで、n は検索する間隔のサイズです。この間隔のサイズは 2 ^j - 2 ^{j - 1} で、上記のようにj = log  iです。つまり、検索する間隔のサイズは 2 ^{log i} - 2 ^{log i - 1} = 2 ^{log i - 1}です。これにより、実行時間は log (2 ^{log i - 1} ) = log ( i ) - 1 = O (log  i ) になります。

これにより、2 つのステージの実行時間を合計して計算されるアルゴリズムの合計実行時間は、O (log  i ) + O (log  i ) = 2 O (log  i ) = O (log  i ) になります。

Bentley と Yao は、指数探索のいくつかのバリエーションを提案しました。^[2]これらのバリエーションは、アルゴリズムの第 2 段階で二分探索の上限を決定するときに、単項探索ではなく二分探索を実行することから成ります。これにより、アルゴリズムの第 1 段階が 2 つの部分に分割され、アルゴリズムは全体として 3 段階アルゴリズムになります。新しい第 1 段階では、以前と同様に、検索キーよりも大きく、検索キーよりも小さい値 を決定します。以前は、 は、次の 2 の累乗を計算することによって単項形式で決定されました (つまり、jに 1 を加算します)。バリエーションでは、代わりに を 2 倍にすることが提案されています (たとえば、 2 ^{2から 2 3}ではなく2 ⁴にジャンプします)。 が検索キーよりも大きい最初のものは、以前よりもはるかに大まかな上限を形成します。これが見つかると、アルゴリズムは第 2 段階に移動し、 と によって形成される区間で二分探索が実行され、より正確な上限指数jが得られます。ここから、アルゴリズムの第 3 段階では、前と同じように、区間 2 ^{j - 1}と 2 ^jでバイナリ検索を実行します。このバリエーションのパフォーマンスは= O (log  i ) です。 ${\displaystyle j'}$${\displaystyle 2^{j'}}$${\displaystyle 2^{j'/2}}$${\displaystyle j'}$${\displaystyle j'}$${\displaystyle j'}$${\displaystyle 2^{j'}}$${\displaystyle j'}$${\displaystyle j'/2}$${\displaystyle j'}$${\displaystyle \lfloor \log i\rfloor +2\lfloor \log(\lfloor \log i\rfloor +1)\rfloor +1}$

Bentley と Yao はこのバリエーションを一般化し、アルゴリズムの最初の段階で任意の数kのバイナリ検索を実行し、 kネストされたバイナリ検索バリエーションを提供します。漸近実行時間はバリエーションによって変化せず、元の指数検索アルゴリズムと同様に O (log  i ) 時間で実行されます。

また、上記のkネストされたバイナリ検索の結果をソートされた配列に使用すると、動的フィンガープロパティのタイトバージョンを持つデータ構造が得られます。 ^[4]これを使用すると、検索中に実行される比較の数はlog( d ) + log log( d ) + ... + O (log  ^* d )となり、ここでdは最後にアクセスされた要素と現在アクセスされている要素のランクの差です。

検索帯域を指数関数的に増加させるアルゴリズムは、グローバルペアワイズアライメントをO(ns)で解決します。ここで、nは配列の長さ、sは配列間の編集距離です。^{[5] [6]}

• 線形探索
• バイナリ検索
• 補間検索
• 三元検索
• ハッシュテーブル