Python 入门指南（四）（1）https://developer.aliyun.com/article/1507399
深度优先搜索
正如其名称所示，该算法在遍历广度之前遍历图中任何特定路径的深度。因此，首先访问子节点，然后访问兄弟节点。它适用于有限图，并需要使用堆栈来维护算法的状态：
def depth_first_search(graph, root): visited_vertices = list() graph_stack = list() graph_stack.append(root) node = root
算法首先创建一个列表来存储已访问的节点。graph_stack堆栈变量用于辅助遍历过程。为了连贯起见，我们使用普通的 Python 列表作为堆栈。
起始节点称为root，并与图的邻接矩阵graph一起传递。root被推入堆栈。node = root保存堆栈中的第一个节点：
while len(graph_stack) > 0: if node not in visited_vertices: visited_vertices.append(node) adj_nodes = graph[node] if set(adj_nodes).issubset(set(visited_vertices)): graph_stack.pop() if len(graph_stack) > 0: node = graph_stack[-1] continue else: remaining_elements = set(adj_nodes).difference(set(visited_vertices)) first_adj_node = sorted(remaining_elements)[0] graph_stack.append(first_adj_node) node = first_adj_node return visited_vertices
while循环的主体将被执行，前提是堆栈不为空。如果node不在已访问节点的列表中，我们将其添加进去。node的所有相邻节点都被adj_nodes = graph[node]收集起来。如果所有相邻节点都已经被访问过，我们就从堆栈中弹出该节点，并将node设置为graph_stack[-1]。graph_stack[-1]是堆栈顶部的节点。continue语句跳回到while循环的测试条件的开头。
另一方面，如果并非所有相邻节点都已经被访问，那么通过使用语句remaining_elements = set(adj_nodes).difference(set(visited_vertices))来找到尚未访问的节点。
在sorted(remaining_elements)中的第一个项目被分配给first_adj_node，并被推入堆栈。然后我们将堆栈的顶部指向这个节点。
当while循环结束时，我们将返回visited_vertices。
对算法进行干扰运行将会很有用。考虑以下图表：
这样一个图的邻接列表如下所示：
graph = dict() graph['A'] = ['B', 'S'] graph['B'] = ['A'] graph['S'] = ['A','G','C'] graph['D'] = ['C'] graph['G'] = ['S','F','H'] graph['H'] = ['G','E'] graph['E'] = ['C','H'] graph['F'] = ['C','G'] graph['C'] = ['D','S','E','F']
节点 A 被选择为我们的起始节点。节点 A 被推入堆栈，并添加到visisted_vertices列表中。这样做时，我们标记它已经被访问。堆栈graph_stack是用简单的 Python 列表实现的。我们的堆栈现在只有 A 一个元素。我们检查节点 A 的相邻节点 B 和 S。为了测试节点 A 的所有相邻节点是否都已经被访问，我们使用 if 语句：
if set(adj_nodes).issubset(set(visited_vertices)): graph_stack.pop() if len(graph_stack) > 0: node = graph_stack[-1] continue
如果所有节点都已经被访问，我们就弹出堆栈的顶部。如果堆栈graph_stack不为空，我们就将堆栈顶部的节点赋给node，并开始另一个while循环主体的执行。语句set(adj_nodes).issubset(set(visited_vertices))将在adj_nodes中的所有节点都是visited_vertices的子集时评估为True。如果 if 语句失败，这意味着还有一些节点需要被访问。我们可以通过remaining_elements = set(adj_nodes).difference(set(visited_vertices))获得这些节点的列表。
从图表中，节点B和S将被存储在remaining_elements中。我们将按字母顺序访问列表：
first_adj_node = sorted(remaining_elements)[0] graph_stack.append(first_adj_node) node = first_adj_node
我们对remaining_elements进行排序，并将第一个节点返回给first_adj_node。这将返回 B。我们通过将其附加到graph_stack来将节点 B 推入堆栈。我们通过将其分配给node来准备访问节点 B。
在while循环的下一次迭代中，我们将节点 B 添加到visited nodes列表中。我们发现 B 的唯一相邻节点 A 已经被访问过。因为 B 的所有相邻节点都已经被访问，我们将其从堆栈中弹出，只留下节点 A。我们返回到节点 A，并检查它的所有相邻节点是否都已经被访问。现在节点 A 只有 S 是未访问的节点。我们将 S 推入堆栈，并重新开始整个过程。
遍历的输出是 A-B-S-C-D-E-H-G-F。
深度优先搜索在解决迷宫问题、查找连通分量和查找图的桥梁等方面有应用。
其他有用的图方法
您经常关心的是找到两个节点之间的路径。您可能还希望找到节点之间的所有路径。另一个有用的方法是找到节点之间的最短路径。在无权图中，这只是它们之间边的最小数量的路径。在加权图中，正如您所见，这可能涉及计算通过一组边的总权重。
当然，在不同的情况下，您可能希望找到最长或最短的路径。
优先队列和堆
优先队列基本上是一种按优先级顺序返回项目的队列类型。这个优先级可以是，例如，最低的项目总是先弹出。虽然它被称为队列，但优先队列通常使用堆来实现，因为对于这个目的来说非常高效。
考虑到，在商店中，顾客排队等候，服务只在队列的前面提供。每个顾客都会花一些时间在队列中等待服务。如果队列中顾客的等待时间分别为 4、30、2 和 1，那么队列中的平均等待时间变为(4 + 34 + 36 + 37)/4，即27.75。然而，如果我们改变服务顺序，使等待时间最短的顾客先接受服务，那么我们会得到不同的平均等待时间。这样做，我们通过(1 + 3 + 7 + 37)/4计算我们的新平均等待时间，现在等于12，一个更好的平均等待时间。显然，按照等待时间最少的顾客开始服务是有益的。按照优先级或其他标准选择下一个项目的方法是创建优先队列的基础。
堆是满足堆属性的数据结构。堆属性规定父节点和其子节点之间必须存在一定的关系。这个属性必须适用于整个堆。
在最小堆中，父节点和子节点之间的关系是父节点必须始终小于或等于其子节点。由于这个关系，堆中最小的元素必须是根节点。
另一方面，在最大堆中，父节点大于或等于其子节点。由此可知，最大值组成了根节点。
从我们刚刚提到的内容中可以看出，堆是树，更具体地说，是二叉树。
虽然我们将使用二叉树，但实际上我们将使用一个列表来表示它。这是可能的，因为堆将存储一个完全二叉树。完全二叉树是指在开始填充下一行之前，每一行必须完全填满：
为了使索引的数学运算更容易，我们将保留列表中的第一项（索引 0）为空。之后，我们将树节点从上到下、从左到右放入列表中：
如果你仔细观察，你会注意到你可以很容易地检索任何节点 n 的子节点。左子节点位于2n，右子节点位于2n + 1。这总是成立的。
我们将看一个最小堆的实现。反过来得到最大堆的逻辑应该不难。
class Heap: def __init__(self): self.heap = [0] self.size = 0
我们用零初始化我们的堆列表，以表示虚拟的第一个元素（请记住，我们只是为了简化数学而这样做）。我们还创建一个变量来保存堆的大小。这不是必需的，因为我们可以检查列表的大小，但我们总是要记得减去一个。所以我们选择保持一个单独的变量。
插入
插入一个项目本身非常简单。我们将新元素添加到列表的末尾（我们理解为树的底部）。然后我们将堆的大小增加一。
但是在每次插入后，如果需要，我们需要将新元素浮动起来。请记住，最小堆中最小的元素需要是根元素。我们首先创建一个名为float的辅助方法来处理这个问题。让我们看看它应该如何行为。想象一下我们有以下堆，并且想要插入值2：
新元素占据了第三行或级别中的最后一个插槽。它的索引值是7。现在我们将该值与其父元素进行比较。父元素位于索引7/2 = 3（整数除法）。该元素持有6，所以我们交换2：
我们的新元素已经被交换并移动到索引3。我们还没有到达堆的顶部（3 / 2 > 0），所以我们继续。我们元素的新父节点在索引3/2 = 1。所以我们比较并且如果需要的话再次交换：
在最后一次交换之后，我们得到了以下堆。请注意它如何符合堆的定义：
接下来是我们刚刚描述的实现：
def float(self, k):
我们将循环直到达到根节点，以便我们可以将元素浮动到需要到达的最高位置。由于我们使用整数除法，一旦我们低于 2，循环就会中断：
while k // 2 > 0:
比较父节点和子节点。如果父节点大于子节点，则交换两个值：
if self.heap[k] < self.heap[k//2]: self.heap[k], self.heap[k//2] = self.heap[k//2], self.heap[k]
最后，不要忘记向上移动树：
k //= 2
这个方法确保元素被正确排序。现在我们只需要从我们的insert方法中调用它：
def insert(self, item): self.heap.append(item) self.size += 1 self.float(self.size)
注意insert中的最后一行调用了float()方法来根据需要重新组织堆。
弹出
就像插入一样，pop()本身是一个简单的操作。我们移除根节点并将堆的大小减一。然而，一旦根节点被弹出，我们需要一个新的根节点。
为了尽可能简单，我们只需取列表中的最后一个项目并将其作为新的根。也就是说，我们将它移动到列表的开头。但现在我们可能不会在堆的顶部有最小的元素，所以我们执行与float操作相反的操作：让新的根节点根据需要下沉。
与插入一样，让我们看看整个操作在现有堆上是如何工作的。想象一下以下堆。我们弹出root元素，暂时使堆没有根：
由于我们不能有一个没有根的堆，我们需要用某物填充这个位置。如果我们选择将一个子节点移上去，我们将不得不弄清楚如何重新平衡整个树结构。所以，我们做一些非常有趣的事情。我们将列表中的最后一个元素移上去填充root元素的位置：
现在这个元素显然不是堆中最小的。这就是我们开始将其下沉的地方。首先我们需要确定将其下沉到哪里。我们比较两个子节点，以便较小的元素将作为根节点下沉时浮动上去：
右子节点显然更小。它的索引是3，代表根索引* 2 + 1。我们继续将我们的新根节点与该索引处的值进行比较：
现在我们的节点跳到了索引3。我们需要将其与较小的子节点进行比较。然而，现在我们只有一个子节点，所以我们不需要担心要与哪个子节点进行比较（对于最小堆来说，它总是较小的子节点）：
这里不需要交换。由于没有更多的行，我们完成了。请再次注意，在sink()操作完成后，我们的堆符合堆的定义。
现在我们可以开始实现这个。在执行sink()方法之前，注意我们需要确定要将父节点与哪个子节点进行比较。好吧，让我们把这个选择放在自己的小方法中，这样代码看起来会简单一些：
def minindex(self, k):
我们可能会超出列表的末尾，在这种情况下，我们返回左子节点的索引：
if k * 2 + 1 > self.size: return k * 2
否则，我们只需返回较小的两个子节点的索引：
elif self.heap[k*2] < self.heap[k*2+1]: return k * 2 else: return k * 2 + 1
现在我们可以创建sink函数：
def sink(self, k):
与之前一样，我们将循环以便将我们的元素下沉到所需的位置：
while k * 2 <= self.size:
接下来，我们需要知道左侧还是右侧的子节点进行比较。这就是我们使用minindex()函数的地方：
mi = self.minindex(k)
就像我们在float()方法中所做的那样，我们比较父节点和子节点，看看是否需要交换：
if self.heap[k] > self.heap[mi]: self.heap[k], self.heap[mi] = self.heap[mi], self.heap[k]
我们需要确保向下移动树，以免陷入循环：
k = mi
现在唯一剩下的就是实现pop()本身。这非常简单，因为sink()方法执行了大部分工作：
def pop(self): item = self.heap[1] self.heap[1] = self.heap[self.size] self.size -= 1 self.heap.pop() self.sink(1) return item
测试堆
现在我们只需要一些代码来测试堆。我们首先创建我们的堆并插入一些数据：
h = Heap() for i in (4, 8, 7, 2, 9, 10, 5, 1, 3, 6): h.insert(i)
我们可以打印堆列表，只是为了检查元素的排序方式。如果你将其重新绘制为树形结构，你应该注意到它满足堆的所需属性：
print(h.heap)
现在我们将一个一个地弹出项目。注意项目是如何按照从低到高的顺序出来的。还要注意每次弹出后堆列表是如何改变的。最好拿出纸和笔，在每次弹出后重新绘制这个列表作为一棵树，以充分理解sink()方法的工作原理：
for i in range(10): n = h.pop() print(n) print(h.heap)
在排序算法的章节中，我们将重新组织堆排序算法的代码。
一旦你的最小堆正常工作并且了解它的工作原理，实现最大堆应该是一项简单的任务。你所需要做的就是颠倒逻辑。
选择算法
选择算法属于一类算法，旨在解决在列表中找到第 i 小元素的问题。当列表按升序排序时，列表中的第一个元素将是列表中最小的项。列表中的第二个元素将是列表中第二小的元素。列表中的最后一个元素将是列表中最小的元素，但也将符合列表中最大的元素。
在创建堆数据结构时，我们已经了解到调用pop方法将返回堆中最小的元素。从最小堆中弹出的第一个元素是列表中第一个最小的元素。同样，从最小堆中弹出的第七个元素将是列表中第七小的元素。因此，要找到列表中第 i 小的元素，我们需要弹出堆i次。这是在列表中找到第 i 小的元素的一种非常简单和高效的方法。
但在第十四章中，选择算法，我们将学习另一种方法，通过这种方法我们可以在列表中找到第 i 小的元素。
选择算法在过滤嘈杂数据、查找列表中的中位数、最小和最大元素以及甚至可以应用于计算机国际象棋程序中。
摘要
本章讨论了图和堆。我们研究了使用列表和字典在 Python 中表示图的方法。为了遍历图，我们研究了广度优先搜索和深度优先搜索。
然后我们将注意力转向堆和优先队列，以了解它们的实现。本章以使用堆的概念来找到列表中第 i 小的元素而结束。
图的主题非常复杂，仅仅一章是不够的。与节点的旅程将在本章结束。下一章将引领我们进入搜索的领域，以及我们可以有效搜索列表中项目的各种方法。
第十二章：搜索
在前面章节中开发的数据结构中，对所有这些数据结构执行的一个关键操作是搜索。在本章中，我们将探讨可以用来在项目集合中查找元素的不同策略。
另一个利用搜索的重要操作是排序。在没有某种搜索操作的情况下，几乎不可能进行排序。搜索的“搜索方式”也很重要，因为它影响了排序算法的执行速度。
搜索算法分为两种广义类型。一种类型假定要对其应用搜索操作的项目列表已经排序，而另一种类型则没有。
搜索操作的性能受到即将搜索的项目是否已经排序的影响，我们将在后续主题中看到。
线性搜索
让我们把讨论重点放在线性搜索上，这是在典型的 Python 列表上执行的。
前面的列表中的元素可以通过列表索引访问。为了在列表中找到一个元素，我们使用线性搜索技术。这种技术通过使用索引从列表的开头移动到末尾来遍历元素列表。检查每个元素，如果它与搜索项不匹配，则检查下一个元素。通过从一个元素跳到下一个元素，列表被顺序遍历。
在处理本章和其他章节中的部分时，我们使用包含整数的列表来增强我们的理解，因为整数易于比较。
无序线性搜索
包含元素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循环的每次迭代中，我们测试搜索项是否等于索引指向的项目。如果为真，则无需继续搜索。我们返回发生匹配的位置。
如果循环运行到列表的末尾，没有找到匹配项，则返回None表示列表中没有这样的项目。
在无序项目列表中，没有关于如何插入元素的指导规则。这影响了搜索的方式。缺乏顺序意味着我们不能依赖任何规则来执行搜索。因此，我们必须逐个访问列表中的项目。如下图所示，对于术语66的搜索是从第一个元素开始的，然后移动到列表中的下一个元素。因此60与66进行比较，如果不相等，我们将66与1、88等进行比较，直到在列表中找到搜索项。
无序线性搜索的最坏情况运行时间为O(n)。在找到搜索项之前，可能需要访问所有元素。如果搜索项位于列表的最后位置，就会出现这种情况。
有序线性搜索
在列表的元素已经排序的情况下，我们的搜索算法可以得到改进。假设元素已按升序排序，搜索操作可以利用列表的有序性使搜索更有效。
算法简化为以下步骤：
- 顺序移动列表。
- 如果搜索项大于循环中当前检查的对象或项目，则退出并返回
None。
在迭代列表的过程中，如果搜索项大于当前项目，则没有必要继续搜索。
当搜索操作开始并且第一个元素与(5)进行比较时，没有匹配。但是因为列表中还有更多元素，搜索操作继续检查下一个元素。继续进行的更有力的原因是，我们知道搜索项可能与大于2的任何元素匹配。
经过第 4 次比较，我们得出结论，搜索项不能在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)。每次迭代将列表减半，遵循元素数量的 log n 进展。
不言而喻，log x假定是指以 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作为中点，这将需要再次运行算法。
以下是典型二分查找与插值查找的更直观的区别。对于典型的二分查找，找到中点的方式如下：
可以看到，中点实际上大致站在前面列表的中间位置。这是通过列表 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的索引。
这张图片只是说明了中点的调整。在插值中，中点很少将列表均分为两半。
另一方面，如果搜索项小于ordered_list[mid_point]处存储的值，那么我们只需要调整index_of_last_element变量指向索引mid_point - 1。这个逻辑被捕捉在 if 语句的 else 部分中index_of_last_element = mid_point - 1。
这张图片展示了重新计算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。
Python 入门指南（四）（3）https://developer.aliyun.com/article/1507403
