1. 首页
  2. 技术文章

Python搜索算法

当您将数据存储在不同的数据结构中时,搜索是非常基本的必要条件。最简单的方法是遍历数据结构中的每个元素,并将其与您要搜索的值相匹配。这称为线性搜索。它效率低下并且很少使用,但是为此创建一个程序可以使我们了解如何实现一些高级搜索算法。

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
版权声明:本文内容由互联网用户贡献,该文观点仅代表作者本人。本站不拥有所有权,不承担相关法律责任。如发现有侵权/违规的内容, 联系QQ1841324605,本站将立刻清除。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

联系我们

服务热线:130-0886-1890

QR code