Python搜尋演算法

將資料儲存在不同的資料結構中時，搜尋是非常基本的必需條件。 最簡單的方法是遍歷資料結構中的每個元素，並將其與要搜尋的值進行匹配。 這就是所謂的線性搜尋。 它效率低下，很少使用。下面建立一個程式演示如何實現一些高階搜尋演算法。

線性搜尋

在這種型別的搜尋中，逐個搜尋所有專案。 每個專案都會被檢查匹配，如果找到匹配項，那麼返回該特定專案，否則搜尋將繼續到資料結構的末尾。

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