Python検索アルゴリズムの補間検索アルゴリズムの実現

一、補間検索アルゴリズム
補間検索アルゴリズムは補間検索とも言われています。これは半角検索アルゴリズムの改良版です。補間検索は、データの分布に従って、数式を利用してキーの位置を予測し、キーのあるシーケンスの範囲を急速に縮小し、データが検索されるまで徐々に接近します。説明によると、補間ルックアップは通常英語辞書を引く方法と似ている。例えば、アルファベットDで始まる英語の単語を調べても、半角検索は決してしません。英語辞書の検索順によると、Dで始まる単語は辞書の前の部分にあるべきで、辞書の前のどこかから探すことができます。キーの索引の計算は、数式は以下の通りです。

middle=left+(target-data[left])/(data[right]-data[left])*(right-left)

パラメータの説明:

middle：求められる境界インデックス。

left：一番左のデータの索引。

target：キー値（目標データ）。

data[left]：左端データ値。

data[right]：最右側データ値。

right：一番右側のデータの索引。

例えば、並べ替えられた数列があります。34、53、57、68、72、81、89、93、99。検索するデータは53です。補間検索の手順は以下の通りです。
ステップ1：データ列を出し、数式を利用して境界値を見つけます。計算プロセスは以下の通りです。
各データを公式に持ち込む：

データを整理するので、求められている索引は2であり、対応するデータは57であり、検索対象データ53と57を下図のように比較する。

ステップ2：53と57を比較した結果、53は57より小さいので、検索57の左半分のデータは、右半分のデータを考慮しないで、インデックス範囲を0と2の間に縮小し、数式を持ち込んだ：

整理した後の索引は1で、対応するデータは53で、検索対象データ53と53を比較して、次の図に示すように、

ステップ3：53と53を比較し、得られた結果は同じで、検索は完了します。説明：何回か分割した後、同じ値が見つからなかったら、このボタンの値はこの数列にないことを表します。
上記のステップ1で分かるように、補間検索アルゴリズムは、半値検索アルゴリズムの取値範囲よりも小さいので、その速度は半値変換法よりも速くなります。これは補間検索アルゴリズムの利点です。
二、例：ユーザーが入力したデータを補間で検索する
ユーザは、任意にデータのセットを入力することができます。例えば、この例には、34、53、57、68、72、81、89、93、99のセットが入力されます。このデータの中で補間ルックアップ方式でそれぞれデータ57、53、93、89、100を検索し、各検索のプロセスを表示する。Pythonコードでこのプロセスを実現します。具体的なコードは以下の通りです。

def insert_search(data, num):
    """
           ：             
    :param data:    data
    :param num:   num
    :return:
    """
    #   
    left_index = 0  #         
    right_index = len(data) - 1  #         
    print("    .......")  #   
    while left_index <= right_index:
        #           
        middle = left_index + (num - data[left_index]) / (data[right_index] - data[left_index]) * (
                right_index - left_index)
        #   
        middle = int(middle)
        # print(middle)
        if num == data[middle]:
            return middle  #          ，      
        elif num < data[middle]:
            #             
            print(f"{num}     {left_index + 1}[{data[left_index]}]    {middle + 1}[{data[middle]}]  ，    ......")
            right_index = middle - 1  #          ，              1
        else:
            #             
            print(f"{num}     {middle + 1}[{data[middle]}]    {right_index + 1}[{data[right_index]}]  ，    ......")
            left_index = middle + 1  #          ，              1
    return -1  #          


inp_num = 0  #     ，      
num_list = [34, 53, 57, 68, 72, 81, 89, 93, 99]  #     
print("     ：")
for index, ele in enumerate(num_list):
    print(f" {index + 1}[{ele}]", end="")  #     
print("")
flag = True  #   ，          

while flag:  #     
    inp_num = int(input("         ：").strip())  #       
    result = insert_search(num_list, inp_num)  #           ――insert_search()  
    if result == -1:  #          -1
        print(f"    [{inp_num}]")  #   -1，       
    else:
        #    -1，      
        print(f" {result + 1}     [{inp_num}]")
    char = input("      ，      ，    y(Y)   n(N)：").strip()
    if char.upper() == "N":
        flag = False

プログラム実行結果は下図のようになります。

ここでPython検索アルゴリズムの補間検索アルゴリズムの実現に関する記事を紹介します。Python補間検索アルゴリズムの内容については、以前の文章を検索したり、次の関連記事を見たりしてください。これからもよろしくお願いします。