Python 搜索算法

將數(shù)據(jù)存儲(chǔ)在不同的數(shù)據(jù)結(jié)構(gòu)中時(shí)，搜索是非?；镜谋匦钘l件。最簡單的方法是遍歷數(shù)據(jù)結(jié)構(gòu)中的每個(gè)元素，并將其與您正在搜索的值進(jìn)行匹配。這就是所謂的線性搜索。它效率低下，很少使用，但為它創(chuàng)建一個(gè)程序給出了我們?nèi)绾螌?shí)現(xiàn)一些高級搜索算法的想法。

線性搜索

在這種類型的搜索中，逐個(gè)搜索所有項(xiàng)目。每個(gè)項(xiàng)目都會(huì)被檢查，如果找到匹配項(xiàng)，那么返回該特定項(xiàng)目，否則搜索將繼續(xù)到數(shù)據(jù)結(jié)構(gòu)的末尾。

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))

當(dāng)上面的代碼被執(zhí)行時(shí)，它會(huì)產(chǎn)生以下結(jié)果 -

True
False

插值搜索

該搜索算法適用于所需值的探測位置。為了使該算法正常工作，數(shù)據(jù)收集應(yīng)該以排序形式并平均分布。最初，探針位置是集合中最大項(xiàng)目的位置。如果匹配發(fā)生，則返回項(xiàng)目的索引。如果中間項(xiàng)目大于項(xiàng)目，則再次在中間項(xiàng)目右側(cè)的子數(shù)組中計(jì)算探針位置。否則，該項(xiàng)目將在中間項(xiàng)目左側(cè)的子數(shù)組中搜索。這個(gè)過程在子數(shù)組上繼續(xù)，直到子數(shù)組的大小減小到零。

有一個(gè)特定的公式來計(jì)算下面的程序中指出的中間位置。

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))

當(dāng)上面的代碼被執(zhí)行時(shí)，它會(huì)產(chǎn)生以下結(jié)果 -

Found 2 at index 0