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

Python

当执行上述代码时，将产生以下结果 -

True
False

Shell

搜索插值

此搜索算法应用于所需值的探测位置。为了使该算法正常工作，数据收集必须有序且均匀分布。首先，探针的位置是集合中最大项目的位置。如果存在匹配项，则返回该项目的索引。如果中间的项目比该项目大，则探针位置会在 子数组 中重新计算到中间项目的右侧。否则，该项目将在 子数组 中搜索到中间项目的左侧。这个过程在子数组的领导下持续进行，直到子数组的规模缩小到零。

有一个特殊的公式来计算中间位置，如下程序所示。看下面的代码实现 -

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

Python

当上面的代码执行时，会产生以下结果 -

Found 2 at index 0