Python検索アルゴリズムの半変換検索アルゴリズムの実装

一、折半検索アルゴリズム
半分の検索アルゴリズムはまた二分検索アルゴリズムと呼ばれ、半分の検索アルゴリズムはデータを二つの等分に分割し、まずキー値（検索するデータ）と中間値で比較します。キーの値が中間値より小さい場合、検索するキーの値が前半にあると確定できます。キーの値が中間値より大きい場合、検索するキーの値は後半になります。そして前半（後半）を分割して、2等分してからキーの値を比較します。このように循環的に比較し、分割して、データを見つけたり、データが存在しないと確定するまで。半値検索の欠点は、初歩的に並べ替えられた数列にのみ適用されます。検索速度が速いのが利点です。
生活の中にも半分の検索に似たような例があります。例えば、数字を当てるゲームです。ゲームを始める前に、まず一定の数字範囲（例えば0～100）を与え、この範囲で当てられる数字を選択します。ユーザーに当てさせて、ユーザーが当てる数字によってヒントを与えます。ユーザーの通常のやり方は、まず広い範囲で適当に数字を言って、大きく当てるようにヒントを与えます。そうすると、数字を当てる範囲を縮小して、ゆっくりと正しい数字を当てることができます。下図のように。このようなやり方は半分に折って検索する方法と似ています。数字の範囲を縮小して数字を決定します。毎回当てる範囲の値が区間の中間値なら、半分にして検索するアルゴリズムです。

例えば、並べ替えられた数列があります。12、45、56、66、77、80、97、101、120、検索するデータは101です。半値検索のステップは以下の通りです。
ステップ1：データ列を出て中間値77を見つけ、101と77を比較し、下図のようにする。

ステップ2：101を77と比較し、101が77より大きいという結果になり、検索するデータは数列の右半分にあるということを説明する。この時は左半分のデータを考えずに、右半分のデータを分割し、中間値を探します。今回の中間値の位置は97と101の間で97を取って、101と97を比較します。

ステップ3：101と97を比較した結果、101が97より大きいと説明したので、検索するデータは右半分の数列にあり、この時は左半分のデータを考慮しないで、残りの数列を分割して、中間値を探します。今回の中間値の位置は101で、101と101を比較します。

ステップ4：101と101を比較し、得られた結果は同等であり、検索は完了する。説明：何回か分割した後、同じ値が見つからなかったら、このボタンの値はこの数列にないことを表します。
半法で検索するステップから見て、明らかに順序検索の回数より少ないです。これは半角検索の利点です。検索のスピードが速いです。
二、例：回線の故障
150メートルの線路がありますが、この線路には故障があります。一日目は修理工が大体いくつかの故障点をロックしました。故障点はそれぞれ路線の12、45、56、66、77、80、97、101、120メートルのところにあります。翌日修理工はこの9つの故障の疑いがあるところの中で本当の故障点を確認します。修理工はこの故障点を素早く調べるために、各データの中間位置から検査を開始します。
例えば、77メートルのところで故障の疑いがある点を電気回路に接続したのは初めてで、彼はこの故障が77メートル後の位置であると判断しました。第二回は97メートルのところの故障の疑いがあります。97メートルの後の位置を説明します。第三回は101メートルのところを取って、再度回線を通して、未接続を発見しました。ここが本当の故障点です。今回の検索は3回を経て、本当の故障点を見つけました。具体的なコードは以下の通りです。

def search(data, num):
    """
          ：             
    :param data:    data
    :param num:   num
    :return:
    """
    low = 0  #           
    high = len(data) - 1  #           
    print("    .......")  #   
    while low <= high and num != -1:
        mid = int((low + high) / 2)  #      
        if num < data[mid]:  #            
            #             
            print(f"{num}         {low + 1}[{data[low]}]        {mid + 1}[{data[mid]}]   ，    ......")
            high = mid - 1  #            1
        elif num > data[mid]:  #            
            #             
            print(f"{num}         {mid + 1}[{data[mid]}]        {high + 1}[{data[high]}]   ，    ......")
            low = mid + 1  #            1
        else:  #            
            return mid  #       
    return -1  #          


inp_num = 0  #     ，      
num_list = [12, 45, 56, 66, 77, 80, 97, 101, 120]  #     
print("       ：")
for index, ele in enumerate(num_list):
    print(f" {index + 1}[{ele}]", end="")  #     
print("")
flag = True  #   ，          

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

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

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