Javaでの内挿検索

1. 前書き

このチュートリアルでは、補間検索アルゴリズムについて説明し、その長所と短所について説明します。 さらに、Javaで実装し、アルゴリズムの時間の複雑さについて説明します。

2. 動機

*補間検索は、均一に分散されたデータ用に調整されたlink:/java-binary-search[binary search]を改良したものです。*
バイナリ検索は、データの分布に関係なく各ステップの検索スペースを半分にします。したがって、時間の複雑さは常に_O(log(n))_です。
一方、*補間検索時間の複雑さは、データの分布*によって異なります。 _O(log(log(n)))_の時間の複雑さを持つ均一に分散されたデータのバイナリ検索よりも高速です。 ただし、最悪のシナリオでは、_O(n)_ほどパフォーマンスが低下する可能性があります。

3. 補間検索

バイナリ検索と同様に、補間検索はソートされた配列でのみ機能します。 各反復で計算された位置にプローブを配置します。 プローブが探しているアイテムに対して正しい場合、位置が返されます。そうでない場合、検索スペースはプローブの右側または左側のいずれかに制限されます。
*プローブ位置の計算は、バイナリ検索と補間検索の唯一の違いです*
バイナリ検索では、プローブの位置は常に残りの検索スペースの一番中央のアイテムです。
それどころか、内挿検索は次の式に基づいてプローブの位置を計算します。
link:/uploads/probe-position-100x15.jpg%20100w []
各用語を見てみましょう。
  • probe:新しいプローブ位置がこのパラメーターに割り当てられます。

  • lowEnd:現在の検索スペースの左端のアイテムのインデックス。

  • highEnd:現在の検索の右端のアイテムのインデックス
    スペース。

  • _data [] _:元の検索スペースを含む配列。

  • item:探しているアイテム。

    補間検索がどのように機能するかをよりよく理解するために、例を使用してそれを示しましょう。
    以下の配列で84の位置を見つけたいとしましょう:
    link:/uploads/step-0-100x36.jpg%20100w []
    配列の長さは8ですので、最初は__highEnd __ = 7および__lowEnd __ = 0です(配列のインデックスは1ではなく0から始まるため)。
    最初のステップでは、プローブ位置の式は_probe_ = 5になります。
    link:/uploads/step-1-100x36.jpg%20100w []
    84(探している_item_)は73(現在の_probe_位置項目)よりも大きいため、次のステップは__lowEnd __ = __probe __ + 1を割り当てることで配列の左側を放棄します。 現在、検索スペースは84と101のみで構成されています。 _probe_位置式は、正確に84のインデックスである__probe __ = 6を設定します。
    link:/uploads/step-2-100x36.jpg%20100w []
    探していたアイテムが見つかったため、位置6が返されます。

*4. Java *での実装

アルゴリズムの仕組みがわかったので、Javaで実装してみましょう。
まず、_lowEnd_および_highEnd_を初期化します。
int highEnd = (data.length - 1);
int lowEnd = 0;
次に、ループを設定し、各反復で、前述の式に基づいて新しい_probe_を計算します。 ループ条件は、_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]);
}
また、新しい_probe_割り当てのたびにアイテムが見つかったかどうかも確認します。
最後に、_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でも実装しました。
このチュートリアルに示されている例は、https://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-3 [Github上]で入手できます。