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