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で実装しましょう。

まず、lowEndhighEndを初期化します。

int highEnd = (data.length - 1);
int lowEnd = 0;

次に、ループを設定し、各反復で、前述の式に基づいて新しいプローブを計算します。 ループ条件は、itemdata[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から入手できます。