データ構造-内挿検索

補間検索は、バイナリ検索の改良版です。この検索アルゴリズムは、必要な値の調査位置で機能します。このアルゴリズムが適切に機能するためには、データ収集はソートされた形式で等しく分散されている必要があります。

バイナリ検索には、線形検索よりも時間の複雑さという大きな利点があります。線形検索にはworst（n）の最悪の複雑さがありますが、バイナリ検索にはΟ（log n）があります。

ターゲットデータの場所が事前にわかっている場合があります。たとえば、電話帳の場合、モルフィウスの電話番号を検索したい場合。ここでは、「M」から始まる名前が保存されているメモリ空間に直接ジャンプできるため、線形検索やバイナリ検索さえも遅く見えるでしょう。

バイナリ検索での配置

バイナリ検索では、目的のデータが見つからない場合、リストの残りの部分は下位と上位の2つの部分に分割されます。どちらかで検索が実行されます。

BSTステップ1 BSTステップ2 BSTステップ3 image:/data_msith bst_step_four.jpg [BSTステップ4]

データがソートされている場合でも、バイナリ検索は目的のデータの位置をプローブするのに利用されません。

内挿検索での位置探索

補間検索は、プローブの位置を計算することにより特定のアイテムを見つけます。最初は、プローブの位置はコレクションの最も中央のアイテムの位置です。

補間ステップ1 補間ステップ2

一致した場合、アイテムのインデックスが返されます。リストを2つの部分に分割するには、次の方法を使用します-

mid = Lo &plus; ((Hi - Lo)/(A[Hi] - A[Lo])) * (X - A[Lo])

where −
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

中央のアイテムがアイテムよりも大きい場合、プローブの位置は中央のアイテムの右側のサブアレイで再び計算されます。それ以外の場合、アイテムは中央のアイテムの左側のサブ配列で検索されます。このプロセスは、サブアレイのサイズがゼロになるまでサブアレイでも継続されます。

補間検索アルゴリズムの実行時の複雑さは、有利な状況でのBSTの*Ο（log n）*と比較して*Ο（log（log n））*です。

アルゴリズム

それは既存のBSTアルゴリズムの即興であるため、位置探査を使用して「ターゲット」データ値インデックスを検索する手順に言及しています-

Step 1 − Start searching data from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new midle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.

疑似コード

A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

   Set Lo  →  0
   Set Mid → -1
   Set Hi  →  N-1

   While X does not match

      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if

      Set Mid = Lo + ((Hi - Lo)/(A[Hi] - A[Lo])) * (X - A[Lo])

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
   End While

End Procedure

Cプログラミング言語での補間検索の実装については、リンク：/data_structures_algorithms/interpolation_search_in_c [ここをクリック]をクリックしてください。

Data-structures-algorithms-interpolation-search-algorithm

データ構造-内挿検索

バイナリ検索での配置

内挿検索での位置探索

アルゴリズム

疑似コード

目次