Python Data Structure 简明教程
Python - Searching Algorithms
在不同的数据结构中存储数据时，搜索是一个非常基本的必要操作。最简单的方法是对数据结构中的每个元素进行遍历，并将其与要搜索的值进行匹配。这称为线性搜索。它效率低下，使用较少，但是为它创建程序可以了解如何实现一些高级搜索算法。
Linear Search
在此类搜索中，对所有项一个接一个地进行顺序搜索。检查每个项，如果找到匹配项，则返回该特定项，否则搜索继续进行，直到数据结构结束。
Example
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))Interpolation Search
此搜索算法根据所需值的探测位置工作。为使此算法正常工作，数据集合应以排序形式分布，并且分布均匀。最初，探测位置是集合中最中间项的位置。如果发生匹配，则返回该项的索引。如果中间项大于该项，则在中间项右边的子数组中再次计算探测位置。否则，在中间项左边的子数组中搜索该项。此过程也会在子数组上继续，直到子数组的大小变为零。
Example
有一个具体公式来计算中间位置，该公式在下面的程序中指示−
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))