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

输出

执行上述代码时，它会产生以下结果 -

插值搜索

此搜索算法适用于所需值的探测位置。要使此算法正常工作，数据收集应采用排序形式并均匀分布。最初，探测位置是集合中最中间项的位置。如果出现匹配项，则返回项目的索引。如果中间项大于项，则再次在中间项右侧的子数组中计算探测位置。否则，将在中间项左侧的子数组中搜索该项。此过程也会在子数组上继续，直到子数组的大小减小到零。

例

有一个特定的公式来计算中间位置，在下面的程序中指示 -

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

输出

执行上述代码时，它会产生以下结果 -