データ構造-補間検索
補間検索は、バイナリ検索の改良版です。この検索アルゴリズムは、必要な値のプロービング位置で機能します。このアルゴリズムが正しく機能するためには、データ収集がソートされた形式で均等に分散されている必要があります。
二分探索には、線形探索よりも時間の複雑さという大きな利点があります。線形探索の複雑さは最悪の場合Ο（n）ですが、二分探索の複雑さはΟ（log n）です。
ターゲットデータの場所が事前にわかっている場合があります。たとえば、電話帳の場合、Morphiusの電話番号を検索する場合です。ここでは、名前が「M」で始まるメモリ空間に直接ジャンプできるため、線形検索やバイナリ検索でさえ遅いように見えます。
二分探索での位置付け
二分探索では、目的のデータが見つからない場合、リストの残りの部分は、下位と上位の2つの部分に分割されます。検索はどちらかで実行されます。
データがソートされている場合でも、バイナリ検索は目的のデータの位置を調べるために利用されません。
補間検索での位置プロービング
補間検索は、プローブ位置を計算することによって特定のアイテムを見つけます。最初、プローブ位置はコレクションの真ん中のアイテムの位置です。
一致する場合は、アイテムのインデックスが返されます。リストを2つの部分に分割するには、次の方法を使用します。
mid = Lo + ((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中央のアイテムがアイテムよりも大きい場合、プローブの位置は、中央のアイテムの右側のサブ配列で再度計算されます。それ以外の場合、アイテムは中央のアイテムの左側にあるサブ配列で検索されます。このプロセスは、サブアレイのサイズがゼロになるまでサブアレイでも続行されます。
補間検索アルゴリズムの実行時の複雑さは Ο(log (log n)) と比較して Ο(log n) 有利な状況でのBSTの。
アルゴリズム
これは既存の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 ProcedureCプログラミング言語での補間検索の実装については、ここをクリックしてください。