Python-検索アルゴリズム

異なるデータ構造にデータを保存する場合、検索は非常に基本的な必要事項です。最も単純な方法は、データ構造内のすべての要素を調べて、検索する値と一致させることです。これは線形検索として知られています。非効率的で、めったに使用されませんが、そのためのプログラムを作成すると、高度な検索アルゴリズムを実装する方法についてのアイデアが得られます。

線形検索

このタイプの検索では、すべてのアイテムを1つずつ順番に検索します。すべてのアイテムがチェックされ、一致が見つかった場合、その特定のアイテムが返されます。それ以外の場合は、データ構造の最後まで検索が続行されます。

def linear_search(values, search_for):
    search_at = 0
    search_res = False

# Match the value with each data element
    while search_at < len(values) and search_res is False:
        if values[search_at] == search_for:
            search_res = True
        else:
            search_at = search_at + 1

    return search_res

l = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(l, 12))
print(linear_search(l, 91))

上記のコードが実行されると、次の結果が生成されます-

True
False

補間検索

この検索アルゴリズムは、必要な値の調査位置で機能します。このアルゴリズムが適切に機能するためには、データ収集はソートされた形式で等しく分散されている必要があります。最初は、プローブの位置はコレクションの最も中央のアイテムの位置です。一致する場合、アイテムのインデックスが返されます。中央のアイテムがアイテムよりも大きい場合、プローブの位置は中央のアイテムの右側のサブアレイで再び計算されます。それ以外の場合、アイテムは中央のアイテムの左側のサブ配列で検索されます。このプロセスは、サブアレイのサイズがゼロになるまでサブアレイでも継続されます。

以下のプログラムに示されている中間位置を計算するための特定の公式があります。

def intpolsearch(values,x ):
    idx0 = 0
    idxn = (len(values) - 1)

    while idx0 <= idxn and x >= values[idx0] and x <= values[idxn]:

# Find the mid point
    mid = idx0 +\
               int(((float(idxn - idx0)/( values[idxn] - values[idx0]))
                    * ( x - values[idx0])))

# Compare the value at mid point with search value
        if values[mid] == x:
            return "Found "+str(x)+" at index "+str(mid)

        if values[mid] < x:
            idx0 = mid + 1
    return "Searched element not in the list"


l = [2, 6, 11, 19, 27, 31, 45, 121]
print(intpolsearch(l, 2))

上記のコードが実行されると、次の結果が生成されます-

Found 2 at index 0

Python-data-structure-python-searching-algorithms

Python-検索アルゴリズム

線形検索

補間検索