Python Data Structure 简明教程
Python - Searching Algorithms
在不同的数据结构中存储数据时，搜索是一个非常基本的必要操作。最简单的方法是对数据结构中的每个元素进行遍历，并将其与要搜索的值进行匹配。这称为线性搜索。它效率低下，使用较少，但是为它创建程序可以了解如何实现一些高级搜索算法。
Searching is a very basic necessity when you store data in different data structures. The simplest approach is to go across every element in the data structure and match it with the value you are searching for.This is known as Linear search. It is inefficient and rarely used, but creating a program for it gives an idea about how we can implement some advanced search algorithms.
Linear Search
在此类搜索中，对所有项一个接一个地进行顺序搜索。检查每个项，如果找到匹配项，则返回该特定项，否则搜索继续进行，直到数据结构结束。
In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data structure.
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
此搜索算法根据所需值的探测位置工作。为使此算法正常工作，数据集合应以排序形式分布，并且分布均匀。最初，探测位置是集合中最中间项的位置。如果发生匹配，则返回该项的索引。如果中间项大于该项，则在中间项右边的子数组中再次计算探测位置。否则，在中间项左边的子数组中搜索该项。此过程也会在子数组上继续，直到子数组的大小变为零。
This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in a sorted form and equally distributed.Initially, the probe position is the position of the middle most item of the collection.If a match occurs, then the index of the item is returned.If the middle item is greater than the item, then the probe position is again calculated in the sub-array to the right of the middle item. Otherwise, the item is searched in the subarray to the left of the middle item. This process continues on the sub-array as well until the size of subarray reduces to zero.
Example
有一个具体公式来计算中间位置，该公式在下面的程序中指示−
There is a specific formula to calculate the middle position which is indicated in the program below −
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))