Javaでの補間検索
1. 序章
このチュートリアルでは、補間検索アルゴリズムについて説明し、その長所と短所について説明します。 さらに、それをJavaで実装し、アルゴリズムの時間計算量について説明します。
2. 動機
補間検索は、均一に分散されたデータ用に調整されたバイナリ検索を改良したものです。
二分探索は、データ分布に関係なく、各ステップの探索空間を半分にするため、時間計算量は常に O(log(n))です。
一方、補間検索時間の複雑さは、データ分布によって異なります。 O(log(log(n)))の時間計算量で、均一に分散されたデータの二分探索よりも高速です。 ただし、最悪のシナリオでは、 O(n)と同じくらいパフォーマンスが低下する可能性があります。
3. 補間検索
二分探索と同様に、補間検索はソートされた配列でのみ機能します。 反復ごとに計算された位置にプローブを配置します。 プローブが探しているアイテムに正しければ、位置が返されます。 それ以外の場合、検索スペースはプローブの右側または左側に制限されます。
プローブ位置の計算は、二分探索と補間探索の唯一の違いです。
二分探索では、プローブ位置は常に残りの探索空間の真ん中の項目です。
逆に、補間検索では、次の式に基づいてプローブ位置が計算されます。
それぞれの用語を見てみましょう。
- probe :新しいプローブ位置がこのパラメーターに割り当てられます。
- lowEnd :現在の検索スペースの左端のアイテムのインデックス。
- highEnd :現在の検索スペースの右端のアイテムのインデックス。
- data [] :元の検索スペースを含む配列。
- item :私たちが探しているアイテム。
補間検索がどのように機能するかをよりよく理解するために、例を使用してそれを示しましょう。
以下の配列で84の位置を見つけたいとしましょう。
配列の長さは8であるため、最初は highEnd =7およびlowEnd = 0です(配列のインデックスは1ではなく0から始まるため)。
最初のステップでは、プローブ位置の式は probe =5になります。
84(探しているアイテム)は73(現在のプローブ位置アイテム)より大きいため、次のステップではを割り当てて配列の左側を破棄します。ローエンド=プローブ+1。 現在、検索スペースは84と101のみで構成されています。 プローブの位置式は、プローブ = 6に設定されます。これは、まさに84のインデックスです。
探していたアイテムが見つかったので、6位に戻ります。
4. Javaでの実装
アルゴリズムがどのように機能するかを理解したので、Javaで実装しましょう。
まず、lowEndとhighEndを初期化します。
int highEnd = (data.length - 1);
int lowEnd = 0;
次に、ループを設定し、各反復で、前述の式に基づいて新しいプローブを計算します。 ループ条件は、itemをdata[lowEnd]およびdata[highEnd] と比較することにより、検索スペースから外れていないことを確認します。
while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) {
int probe
= lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]);
}
また、プローブを新たに割り当てるたびに、アイテムが見つかったかどうかを確認します。
最後に、lowEndまたはhighEndを調整して、各反復の検索スペースを減らします。
public int interpolationSearch(int[] data, int item) {
int highEnd = (data.length - 1);
int lowEnd = 0;
while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) {
int probe
= lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]);
if (highEnd == lowEnd) {
if (data[lowEnd] == item) {
return lowEnd;
} else {
return -1;
}
}
if (data[probe] == item) {
return probe;
}
if (data[probe] < item) {
lowEnd = probe + 1;
} else {
highEnd = probe - 1;
}
}
return -1;
}
5. 結論
この記事では、例を使用して補間検索について説明しました。 Javaでも実装しました。
このチュートリアルに示されている例は、Githubでから入手できます。