使用前面章节中开发的数据结构，对所有数据结构执行的一个关键操作是搜索。在本章中，我们将探讨可用于在项目集合中查找元素的不同策略。
利用搜索的另一个重要操作是排序。如果没有搜索操作的变体，几乎不可能进行排序。“搜索方式”也很重要，因为它关系到排序算法最终执行的速度。
搜索算法分为两大类。一个类别假设要应用搜索操作的项目列表已排序，而另一个类别则未排序。
搜索操作的性能很大程度上受将要搜索的项目是否已排序的影响，我们也将在后面的主题中看到这一点。
让我们集中讨论在典型 Python 列表上执行的线性搜索。
前面的列表包含可通过列表索引访问的元素。为了在列表中找到一个元素，我们采用了线性搜索技术。这种技术通过使用索引从列表的开头移动到末尾，遍历元素列表。检查每个元素，如果它与搜索项目不匹配，则检查下一个项目。通过从一个项目跳到下一个项目，列表按顺序遍历。
In treating the sections in this chapter and others, we use a list with integers to enhance our understanding since integers lend themselves to easy comparison.
包含元素60、1、88、10和100的列表是无序列表的示例。列表中的项目没有数量级。要在这样的列表上执行搜索操作，从第一个项目开始，将其与搜索项目进行比较。如果未进行匹配，则检查列表中的下一个元素。这会一直持续到我们到达列表中的最后一个元素，或者直到匹配完成。
def search(unordered_list, term):
unordered_list_size = len(unordered_list)
for i in range(unordered_list_size):
if term == unordered_list[i]:
return i
return None search函数以包含我们的数据的列表和我们正在查找的项目为参数，称为搜索词。
获取数组的大小并确定执行for循环的次数。
if term == unordered_list[i]:
... 在for循环的每一次过程中，我们测试搜索项是否等于索引所指向的项。如果为 true，则无需继续搜索。我们返回比赛发生的位置。
如果循环运行到列表的末尾，但没有进行匹配，则返回None，表示列表中没有此类项。
在无序的项目列表中，没有关于如何插入元素的指导规则。因此，这会影响搜索的方式。缺乏秩序意味着我们不能依赖任何规则来执行搜索。因此，我们必须逐一访问清单中的项目。如下图所示，对术语66的搜索从第一个元素开始，然后移动到列表中的下一个元素。因此，将60与66进行比较，如果不相等，我们将66与1、88等进行比较，直到在列表中找到搜索项。
无序线性搜索的最坏情况运行时间为O(n)。在查找搜索词之前，可能需要访问所有元素。如果搜索词位于列表的最后一个位置，则会出现这种情况。
在列表元素已经排序的情况下，我们的搜索算法可以改进。假设元素已按升序排序，搜索操作可以利用列表的有序性，使搜索更高效。
算法简化为以下步骤：
- 按顺序在列表中移动。
- 如果搜索项目大于循环中当前正在检查的对象或项目，则退出并返回 None。
在遍历列表的过程中，如果搜索项大于当前项，则无需继续搜索。
当搜索操作开始并且第一个元素与（5进行比较时，不进行匹配。但由于列表中有更多元素，搜索操作将继续检查下一个元素。一个更令人信服的理由是，我们知道搜索项可能匹配大于2的任何元素。
经过第四次比较，我们得出结论，在6所在的任何位置都找不到搜索项。换句话说，如果当前项大于搜索项，则表示无需进一步搜索列表。
def search(ordered_list, term):
ordered_list_size = len(ordered_list)
for i in range(ordered_list_size):
if term == ordered_list[i]:
return i
elif ordered_list[i] > term:
return None
return None if声明现在迎合了这张支票。elif部分测试ordered_list[i] > term的条件。如果比较结果为True，则该方法返回None。
方法中的最后一行返回None，因为循环可能会遍历列表，但仍然找不到任何与搜索项匹配的元素。
有序线性搜索的最坏情况时间复杂度为O(n)。通常，这种搜索被认为效率低下，尤其是在处理大型数据集时。
二进制搜索是一种搜索策略，通过不断减少要搜索的数据量，从而提高搜索词的找到率，来查找列表中的元素。
要使用二进制搜索算法，必须对要操作的列表进行排序。
二进制术语具有许多含义，有助于我们正确理解算法。
每次尝试查找列表中的项目时，必须做出二元决策。一个关键的决定是猜测列表的哪一部分可能包含我们正在寻找的项目。搜索词会出现在列表的前半部分还是后半部分，也就是说，如果我们总是认为列表由两部分组成的话？
如果我们使用一种经过教育的猜测策略，而不是从列表的一个单元格移动到另一个单元格，那么我们很可能会到达一个位置，在那里可以更快地找到项目。
作为一个例子，我们想找到 1000 页书的中间页。我们已经知道，每本书都有从 1 开始按顺序编号的页码。所以它认为第 500 页应该在书的正中找到，而不是从第 1 页、第 2 页移动和翻转到第 500 页。假设我们现在决定查找第 250 页。我们仍然可以使用我们的策略轻松找到页面。我们猜第 500 页把书一分为二。第 250 页，将放在书的左边。不必担心我们是否能在第 500 页和第 1000 页之间找到第 250 页，因为在那里永远找不到它。因此，使用第 500 页作为参考，我们可以打开大约一半位于第 1 页和第 500 页之间的页面。这使我们更接近于找到第 250 页。
以下是对有序项目列表执行二进制搜索的算法：
def binary_search(ordered_list, term):
size_of_list = len(ordered_list) - 1
index_of_first_element = 0
index_of_last_element = size_of_list
while index_of_first_element <= index_of_last_element:
mid_point = (index_of_first_element + index_of_last_element)/2
if ordered_list[mid_point] == term:
return mid_point
if term > ordered_list[mid_point]:
index_of_first_element = mid_point + 1
else:
index_of_last_element = mid_point - 1
if index_of_first_element > index_of_last_element:
return None 假设我们必须找到10项在列表中的位置，如下所示：
该算法使用while循环来迭代调整列表中的限制，在该限制内查找搜索项。只要启动索引index_of_first_element和index_of_last_element索引之间的差值为正，while循环将运行。
该算法首先通过将第一个元素（0的索引添加到最后一个元素（4的索引中，并将其除以2来找到列表的中点，从而找到中间索引mid_point。
mid_point = (index_of_first_element + index_of_last_element)/2 在这种情况下，在列表的中间位置或索引处找不到10。如果我们搜索的是120，我们必须将index_of_first_element调整为mid_point +1。但由于10位于列表的另一边，我们将index_of_last_element调整为mid_point-1：
我们的新指数index_of_first_element和index_of_last_element现在分别为0和1，我们计算中间值(0 + 1)/2，等于0。新的中点是0，我们找到中间项并与搜索项ordered_list[0]进行比较，得到值10。瞧！找到了我们的搜索词。
通过重新调整index_of_first_element和index_of_last_element的索引，只要index_of_first_element小于index_of_last_element，我们的列表大小就会减少一半。如果情况并非如此，则很可能我们的搜索词不在列表中。
这里的实现是迭代的。我们还可以应用移动标记搜索列表开始和结束的指针的相同原理，开发算法的递归变体。
def binary_search(ordered_list, first_element_index, last_element_index, term):
if (last_element_index < first_element_index):
return None
else:
mid_point = first_element_index + ((last_element_index - first_element_index) / 2)
if ordered_list[mid_point] > term:
return binary_search(ordered_list, first_element_index, mid_point-1,term)
elif ordered_list[mid_point] < term:
return binary_search(ordered_list, mid_point+1, last_element_index, term)
else:
return mid_point 对二进制搜索算法递归实现的调用及其输出如下：
store = [2, 4, 5, 12, 43, 54, 60, 77]
print(binary_search(store, 0, 7, 2))
Output:
>> 0递归二进制搜索和迭代二进制搜索之间的唯一区别是函数定义和计算mid_point的方式。((last_element_index - first_element_index) / 2)操作后的mid_point计算必须将其结果添加到first_element_index。这样我们就可以定义列表中尝试搜索的部分。
二进制搜索算法的最差时间复杂度为O(log n)。在每次迭代中，列表的一半在元素数 logn 之后。
It goes without saying that in log x is assumed to be referring to log base 2.
二进制搜索算法还有另一种变体，可以说它更接近于模仿人类对任何项目列表进行搜索的方式。它仍然是基于对排序后的项目列表中可能找到搜索项目的位置进行良好猜测。
例如，检查以下项目列表：
要找到120，我们需要查看列表的右侧部分。我们对二进制搜索的初始处理通常首先检查中间元素，以确定它是否匹配搜索项。
更人性化的做法是选择一个中间元素，这样不仅可以将数组一分为二，而且可以尽可能接近搜索词。使用以下规则计算中间位置：
mid_point = (index_of_first_element + index_of_last_element)/2 我们将用一个更好的公式来代替这个公式，使我们更接近搜索项。mid_point将接收nearest_mid函数的返回值。
def nearest_mid(input_list, lower_bound_index, upper_bound_index, search_value):
return lower_bound_index + (( upper_bound_index -lower_bound_index)/ (input_list[upper_bound_index] -input_list[lower_bound_index])) * (search_value -input_list[lower_bound_index]) nearest_mid函数将执行搜索的列表作为参数。lower_bound_index和upper_bound_index参数表示我们希望在其中找到搜索项的列表中的边界。search_value表示正在搜索的值。
公式中使用了这些参数：
lower_bound_index + (( upper_bound_index - lower_bound_index)/ (input_list[upper_bound_index] - input_list[lower_bound_index])) * (search_value - input_list[lower_bound_index]) 根据我们的搜索列表44、60、75、100、120、230和250，将使用以下值计算nearest_mid：
lower_bound_index = 0
upper_bound_index = 6
input_list[upper_bound_index] = 250
input_list[lower_bound_index] = 44
search_value = 230现在可以看到，mid_point将收到值5，这是我们搜索词位置的索引。二进制搜索会选择100作为 mid，这将需要再次运行该算法。
下面给出了一个更直观的示例，说明了典型的二进制搜索与插值的区别。对于典型的二进制搜索，查找中点如下：
可以看到，中点实际上是站在前面列表的中间。这是除以列表 2 的结果。
另一方面，插值搜索会这样移动：
在插值搜索中，我们的中点向左或向右摆动得更多。这是由除法获得中点时使用的乘数效应造成的。从上图中，我们的中点已向右倾斜。
除了计算中间位置的方式外，插值算法的其余部分与二进制搜索相同。
def interpolation_search(ordered_list, term):
size_of_list = len(ordered_list) - 1
index_of_first_element = 0
index_of_last_element = size_of_list
while index_of_first_element <= index_of_last_element:
mid_point = nearest_mid(ordered_list, index_of_first_element, index_of_last_element, term)
if mid_point > index_of_last_element or mid_point < index_of_first_element:
return None
if ordered_list[mid_point] == term:
return mid_point
if term > ordered_list[mid_point]:
index_of_first_element = mid_point + 1
else:
index_of_last_element = mid_point - 1
if index_of_first_element > index_of_last_element:
return None nearest_mid函数使用乘法运算。这会产生大于upper_bound_index或小于lower_bound_index的值。出现这种情况时，表示搜索词term不在列表中。因此返回None以表示这一点。
那么当ordered_list[mid_point]不等于搜索它们时会发生什么呢？好的，我们现在必须重新调整index_of_first_element和index_of_last_element，以便算法将重点放在数组中可能包含搜索项的部分。这正是我们在二进制搜索中所做的。
if term > ordered_list[mid_point]:
index_of_first_element = mid_point + 1 如果搜索项大于存储在ordered_list[mid_point]的值，则我们只调整index_of_first_element变量以指向索引mid_point + 1。
下图显示了如何进行调整。调整index_of_first_element并指向mid_point+1.的指标
The image only illustrates the adjustment of the midpoint. In interpolation rarely does the midpoint divide the list in 2 equal halves.
另一方面，如果搜索项小于存储在ordered_list[mid_point]的值，则我们只调整index_of_last_element变量以指向索引mid_point - 1。此逻辑在 if 语句index_of_last_element = mid_point - 1的 else 部分中捕获。
图中显示了重新计算index_of_last_element对中点位置的影响。
让我们用一个更实际的例子来了解二进制搜索和插值算法的内部工作原理。
以包含以下元素的列表为例：
[ 2, 4, 5, 12, 43, 54, 60, 77] 在索引 0 处存储 2，在索引 7 处找到值 77。现在，假设我们想要在列表中找到元素 2。这两种不同的算法将如何进行？
如果我们将此列表传递给插值search函数，nearest_mid函数将返回一个等于0的值。只要比较一下，我们就会找到搜索词。
另一方面，二进制搜索算法需要进行三次比较才能得出如下图所示的搜索项：
第一个mid_point计算为3。第二个mid_point是1，找到搜索词的最后一个mid_point是0。
二进制搜索和插值搜索操作的性能优于有序和无序线性搜索函数。由于顺序探测列表中的元素以查找搜索项，有序和无序线性搜索的时间复杂度为O(n)。当列表很大时，这会导致非常差的性能。
另一方面，只要尝试搜索，二进制搜索操作就会将列表一分为二。在每次迭代中，我们比线性策略更快地接近搜索项。时间复杂度产生O(log n)。尽管使用二进制搜索的速度有所提高，但最重要的是它不能用于未排序的项目列表，也不建议用于较小的项目列表。
找到包含搜索词的列表部分的能力在很大程度上决定了搜索算法的性能。在插值搜索算法中，计算 mid，从而提高获得搜索项的概率。插值搜索的时间复杂度为O( log ( log n))。与二进制搜索相比，这种搜索速度更快。
在本章中，我们研究了两种搜索算法。讨论了线性搜索算法和二进制搜索算法的实现，并进行了比较。本节还讨论了二进制搜索变量插值搜索。了解使用哪种搜索操作将在后续章节中介绍。
在下一章中，我们将使用所获得的知识对项目列表执行排序操作。