二分查找

如何在Python中进行二进制搜索

立即观看 本教程有一个由Real Python团队制作的相关视频课程。将其与书面教程一起观看，以加深理解。在Python中创建一个二进制搜索

二进制搜索是计算机科学中的一个经典算法。它经常出现在编程比赛和技术面试中。实现二进制搜索原来是一项具有挑战性的任务，即使你理解了这个概念。除非你很好奇或者有特定的任务，否则你应该总是利用现有的库来在Python或其他语言中进行二进制搜索。

在本教程中，你将学习如何。

使用 bisect 模块在 Python 中进行二进制搜索 在 Python 中以递归和迭代的方式实现二进制搜索 识别并修复二进制搜索Python实现中的缺陷 分析二进制搜索算法的时空复杂性 比二进制搜索还要快的搜索 本教程假定你是一个学生或对算法和数据结构感兴趣的中级程序员。至少，你应该熟悉 Python 的内置数据类型，如列表和图元。此外，对递归、类、数据类和 lambdas 的一些熟悉将有助于你更好地理解你将在本教程中看到的概念。

下面你会发现一个链接，指向本教程中你将看到的示例代码，它需要 Python 3.7 或更高版本才能运行。

获取示例代码。点击这里，获取本教程中学习Python二进制搜索的示例代码。

基准测试 在本教程的下一节，你将使用互联网电影数据库（IMDb）的一个子集，对一些搜索算法的性能进行基准测试。这个数据集对个人和非商业使用是免费的。它以一堆压缩的制表符分隔值（TSV）文件的形式分发，每天都有更新。

为了使你的生活更轻松，你可以使用样本代码中的Python脚本。它将自动从IMDb获取相关文件，解压，并提取有趣的部分。

$ python download_imdb.py

从IMDb获取数据... 创建了 "names.txt "和 "sorted_names.txt"。 请注意，这将下载和提取大约600MB的数据，并产生两个额外的文件，其大小约为该数据的一半。下载以及对这些数据的处理，可能需要一两分钟才能完成。

下载IMDb 要手动获取数据，请将你的网络浏览器导航到

https://datasets.imdbws.com/，
并抓取名为name.basics.tsv.gz

的文件，其中包含演员、导演、编剧等的记录。当你解压该文件时，你会看到以下内容。

nconst primaryName 出生年月 死亡年月 (...)
nm0000001 Fred Astaire 1899 1987 (...)
nm0000002 劳伦-巴考尔 1924 2014 (...)
nm0000003 Brigitte Bardot 1934 (...)
nm0000004 John Belushi 1949 1982 (...)

它有一个标题，第一行是列名，后面的每一行都是数据记录。每条记录包含一个唯一的标识符、全名、出生年份和其他一些属性。这些都是以制表符为界的。

有数以百万计的记录，所以不要试图用普通的文本编辑器来打开这个文件，以免使你的电脑崩溃。即使是专门的软件，如电子表格，在打开它时也会有问题。相反，你可以利用JupyterLab中的高性能数据网格查看器，例如。

读取以制表符分隔的数值 有几种方法可以解析TSV文件。例如，你可以用Pandas读取它，使用一个专门的应用程序，或者利用一些命令行工具。然而，建议你使用样本代码中包含的无障碍Python脚本。

注意：作为一条经验法则，你应该避免手动解析文件，因为你可能会忽略边缘情况。例如，在其中一个字段中，分隔符Tab可以在引号内按字面意思使用，这将破坏列的数量。只要有可能，尽量在标准库中找到一个相关的模块，或者一个值得信赖的第三方模块。

最终，你希望最终有两个文本文件供你使用。

names.txt 排序后的名字.txt 其中一个将包含一个从原始TSV文件中剪掉第二列而得到的名字列表。

弗雷德-阿斯泰尔 劳伦-巴考尔 碧姬-芭铎 约翰-贝鲁斯 英格玛-伯格曼 ... 第二个将是这个的分类版本。

一旦两个文件都准备好了，你就可以用这个函数把它们加载到Python中。

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

这段代码返回一个从给定文件中提取的名字列表。请注意，对结果字符串调用.splitlines()可以删除尾部的换行符。 请注意，在生成的字符串上调用.splitlines()会删除每行的尾部换行符。作为一个替代方法，你可以调用text_file.readlines()，但这将保留不需要的换行符。

测量执行时间 为了评估一个特定算法的性能，你可以根据IMDb数据集测量其执行时间。这通常是在内置的time或timeit模块的帮助下完成的，这些模块对于代码块的计时很有用。

如果你想的话，你也可以定义一个自定义装饰器来为一个函数计时。所提供的示例代码使用了Python 3.7中引入的time.perf_counter_ns()，因为它提供了纳秒级的高精确度。

了解搜索算法 搜索是无处不在的，是计算机科学的核心。光是今天你可能就做了几次网络搜索，但你有没有想过搜索的真正含义？

搜索算法有许多不同的形式。例如，你可以

做一个全文搜索 用模糊搜索匹配字符串 寻找图形中的最短路径 查询一个数据库 寻找一个最小或最大的值 在本教程中，你将学习如何在一个排序的项目列表中搜索一个元素，如电话簿。当你搜索这样一个元素时，你可能会问以下问题之一。

问题 答案 它在那里吗？ 有 它在哪里？ 在第42页 是哪个人？ 一个叫John Doe的人 第一个问题的答案告诉你一个元素是否存在于这个集合中。它总是保持真或假。第二个答案是一个元素在集合中的位置，如果该元素缺失，它可能是不可用的。最后，第三个答案是元素本身，或缺少元素。

注意：有时由于重复或类似的项目，可能会有一个以上的正确答案。例如，如果你有几个名字相同的联系人，那么他们都会符合你的搜索标准。在其他时候，可能只有一个近似的答案或根本没有答案。

在最常见的情况下，你会通过价值进行搜索，将集合中的元素与你提供的确切的元素作为参考进行比较。换句话说，你的搜索标准是整个元素，比如一个数字、一个字符串，或者一个像人一样的物体。即使两个被比较的元素之间有最微小的差异，也不会导致匹配。

另一方面，你可以通过选择一个元素的某些属性，如一个人的姓氏，来对你的搜索标准进行更细化。这被称为按键搜索，因为你选择一个或多个属性进行比较。在你深入研究Python中的二进制搜索之前，让我们快速浏览一下其他的搜索算法，以获得更大的视野并了解它们是如何工作的。

随机搜索 你可能会在你的背包里找什么东西？你可能只是把手伸进背包，随机挑选一件物品，然后看看是否是你想要的那件。如果你不走运，那么你就把东西放回去，冲洗，然后重复。这个例子是理解随机搜索的好方法，它是效率最低的搜索算法之一。这种方法的低效率源于这样一个事实，即你有可能多次挑选到相同的错误东西。

注：有趣的是，从理论上讲，如果你非常幸运或者集合中的元素数量很少，这种策略可能是最有效的策略。

这个算法的基本原理可以用下面一段Python代码来表达。

import random
def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

这个函数一直循环到随机选择的某个元素与输入的值相匹配。然而，这并不十分有用，因为该函数要么隐含地返回None，要么返回它在参数中已经收到的相同的值。你可以在下面的链接中找到可供下载的示例代码的完整实现。

获取示例代码。点击这里获得你在本教程中用来学习Python二进制搜索的示例代码。

对于微观的数据集，随机搜索算法似乎在合理地快速完成它的工作。

>>>
>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

然而，想象一下，要在数以百万计的元素中进行这样的搜索! 下面是针对IMDb数据集所做的性能测试的简要介绍。

Search Term Element Index Best Time Average Time Worst Time

搜索词 元素索引 最佳时间 平均时间 最差时间

Fred Astaire 0 0.74s 21.69s 43.16s
Alicia Monica 4,500,000 1.02s 26.17s 66.34s
Baoyin Liu 9,500,000 0.11s 17.41s 51.03s
missing N/A 5m 16s 5m 40s 5m 54s

不同内存位置的独特元素被特别选择以避免偏差。每个词被搜索了十次，以考虑到算法的随机性和其他因素，如垃圾收集或系统进程在后台运行。

注意：如果你想自己进行这个实验，那么请参考本教程介绍中的说明。为了测量你的代码的性能，你可以使用内置的时间和timeit模块，或者你可以用自定义的装饰器为函数计时。

该算法具有非决定性的性能。虽然找到一个元素的平均时间并不取决于它的位置，但最佳和最差的时间却相差两到三个数量级。它还存在着不一致的行为。考虑到有一个包含一些重复的元素的集合。因为该算法是随机挑选元素的，所以在随后的运行中它将不可避免地返回不同的副本。

你怎么能改进这个问题呢？一种同时解决这两个问题的方法是使用线性搜索。

线性搜索 当你决定午餐吃什么时，你可能会在菜单上乱七八糟地寻找，直到有东西吸引你的注意。或者，你可以采取一种更系统的方法，从上到下扫描菜单，按顺序仔细检查每一个项目。简而言之，这就是线性搜索。为了在Python中实现它，你可以枚举()元素来跟踪当前元素的索引。

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

这个函数以预定义的、一致的顺序在一个元素集合上循环。当元素被找到，或者没有更多的元素需要检查时，它就停止。这个策略保证了没有元素被多次访问，因为你是按照索引的顺序遍历它们。

让我们看看线性搜索对你之前使用的IMDb数据集的处理情况。

搜索词 元素 索引 最佳时间 平均时间 最差时间

Fred Astaire 0 491ns 1.17µs 6.1µs
Alicia Monica 4,500,000 0.37s 0.38s 0.39s
Baoyin Liu 9,500,000 0.77s 0.79s 0.82s
missing N/A 0.79s 0.81s 0.83s

单个元素的查询时间几乎没有任何差异。平均时间与最佳和最差的时间几乎相同。由于元素总是以相同的顺序浏览，寻找同一元素所需的比较次数并没有变化。

然而，查找时间随着元素在集合中的索引增加而增长。该元素离列表的开头越远，需要运行的比较就越多。在最坏的情况下，当一个元素丢失时，必须检查整个集合才能给出一个明确的答案。

当你把实验数据投射到一个图上并把这些点连接起来时，那么你会立即看到元素位置和找到它所需的时间之间的关系。

线性搜索性能 所有的样本都位于一条直线上，可以用一个线性函数来描述，这就是算法名称的由来。你可以假设，平均而言，使用线性搜索找到任何元素所需的时间将与集合中所有元素的数量成正比。随着要搜索的数据量的增加，它们的规模并不大。

例如，在一些机场可用的生物识别扫描仪，如果使用线性搜索来实现，就不会在几秒钟内识别出乘客。另一方面，对于较小的数据集来说，线性搜索算法可能是一个不错的选择，因为它不需要对数据进行预处理。在这种情况下，预处理的好处是无法偿还其成本的。

Python 已经提供了线性搜索，所以没有必要自己编写它。例如，列表数据结构暴露了一个方法，它将返回一个元素的索引或引发一个异常。

>>>
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

这也可以告诉你该元素是否存在于集合中，但更多的Pythonic方法是使用多功能的操作符。

>>>
>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

值得注意的是，尽管在引擎盖下使用了线性搜索，但这些内置的函数和运算符会让你的实现大打折扣。这是因为它们是用纯 C 编写的，可以编译成本地机器代码。标准的 Python 解释器是无法与之匹敌的，无论你如何努力。

用 timeit 模块进行的快速测试表明，Python 实现的运行速度可能比同等的本地实现慢十倍。

import timeit
from search.linear import contains
fruits = ['orange', 'plum', 'banana', 'apple']
timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

然而，对于足够大的数据集，即使是本地代码也会遇到它的极限，唯一的解决办法是重新思考算法。

注意：in运算符并不总是做线性搜索。例如，当你在一个集合上使用它时，它会做一个基于哈希的搜索。该操作符可以与任何可迭代的对象一起工作，包括元组、列表、集合、dict和str。你甚至可以通过实现神奇的方法 .contains() 来定义底层逻辑，用它支持你的自定义类。

在现实生活场景中，通常应该避免使用线性搜索算法。例如，有一次我没能在兽医诊所登记我的猫，因为他们的系统总是崩溃。医生告诉我，他最终必须升级他的电脑，因为向数据库中添加更多的记录会使它运行得越来越慢。

我记得当时我就在想，写那个软件的人显然不知道二进制搜索算法！"。

二进制搜索 二进制这个词一般与数字2有关。在这里，它指的是将一个元素集合分成两半，并在算法的每一步丢掉其中的一个。这可以极大地减少寻找一个元素所需的比较次数。但是有一个问题--必须先对集合中的元素进行排序。

这背后的想法类似于在一本书中寻找一页的步骤。一开始，你通常会打开书，找到一个完全随机的页面，或者至少是一个接近于你认为你想要的页面的页面。

偶尔，你会很幸运地在第一次尝试时就能找到那一页。然而，如果页码太低，那么你就知道这一页一定是在右边。如果你在下一次尝试时超额完成任务，并且当前的页码高于你要找的那一页，那么你就可以肯定，它一定是在这两者之间。

你重复这个过程，但不是随机选择一个页面，而是检查位于这个新范围正中间的页面。这样可以最大限度地减少尝试的次数。类似的方法可以用在数字猜测游戏中。如果你没有听说过这个游戏，那么你可以在互联网上查找，得到大量的用Python实现的例子。

注意：有时，如果数值是均匀分布的，你可以用线性插值来计算中间指数，而不是取平均值。这种算法的变化将需要更少的步骤。

限制要搜索的页面范围的页码被称为下限和上限。在二进制搜索中，你通常以第一页为下限，以最后一页为上限开始。你必须边走边更新这两个界限。例如，如果你翻到的那一页比你要找的那一页低，那么这就是你的新下限。

假设你在一个按大小升序排序的水果集合中寻找一个草莓。

按照大小升序排列的水果 在第一次尝试中，中间的元素恰好是柠檬。由于它比草莓大，你可以放弃右边的所有元素，包括柠檬。你会把上界移到一个新的位置，并更新中间的索引。

水果的大小按升序排列 现在，你只剩下开始时的一半的水果了。当前的中间元素确实是你要找的草莓，这就结束了搜索。如果它不是，那么你就会相应地更新边界，并继续下去，直到它们互相通过。例如，在草莓和猕猴桃之间寻找一个失踪的李子，结果如下。

果实的大小升序排列 请注意，为了找到所需的元素，并没有进行那么多的比较。这就是二进制搜索的神奇之处。即使你要处理一百万个元素，你也最多只需要少量的检查。由于减半的原因，这个数字不会超过元素总数的对数底2。换句话说，剩余元素的数量在每一步都会减少一半。

这是有可能的，因为元素已经按大小排序了。然而，如果你想通过另一个键来寻找水果，例如颜色，那么你就必须再次对整个集合进行排序。为了避免昂贵的排序开销，你可以尝试提前计算同一个集合的不同视图。这有点类似于创建一个数据库索引。

考虑一下如果你在一个集合中增加、删除或更新一个元素会发生什么。为了使二进制搜索继续工作，你需要保持适当的排序顺序。这可以通过 bisect 模块来实现，你将在下一节中看到这个模块。

在本教程的后面，你将看到如何在 Python 中实现二进制搜索算法。现在，让我们用IMDb数据集来对抗它。请注意，要搜索的人与以前不同。这是因为数据集必须为二进制搜索进行排序，而二进制搜索会对元素重新排序。新元素的位置与之前的指数大致相同，以保持测量的可比性。

搜索词元素索引平均时间比较

(…) Berendse 0 6.52µs 23
Jonathan Samuangte 4,499,997 6.99µs 24
Yorgos Rahmatoulin 9,500,001 6.5µs 23

missing N/A 7.2µs 23
失踪 不适用 7.2µs 23

答案几乎是瞬时的。在平均情况下，二进制搜索只需要几微秒就能在所有900万个元素中找到一个元素！这也是一个很好的例子。除此以外，所选元素的比较次数几乎保持不变，这与下面的公式相吻合。

比较次数的公式 找到大多数元素需要最多的比较次数，这可以从集合的大小的对数中得出。反之，中间只有一个元素可以通过一次比较就能找到。

二进制搜索是分而治之技术的一个很好的例子，它把一个问题分割成一堆同类的小问题。然后将各个解决方案结合起来，形成最终的答案。这种技术的另一个著名例子是Quicksort算法。

注意：不要把 "分而治之 "与动态编程混为一谈，后者是一种有点类似的技术。

与其他搜索算法不同的是，二进制搜索的用途不仅仅是搜索。例如，它允许进行集合成员测试，寻找最大或最小的值，寻找目标值的最近邻居，执行范围查询，等等。

如果速度是重中之重，那么二进制搜索就不一定是最好的选择。甚至有更快的算法可以利用基于哈希的数据结构的优势。然而，这些算法需要大量的额外内存，而二进制搜索则提供了一个良好的空间-时间权衡。

删除广告 基于哈希值的搜索 为了更快地搜索，你需要缩小问题空间。二进制搜索通过在每一步将候选人的数量减半来实现这一目标。这意味着，即使你有一百万个元素，在所有元素都被排序的前提下，最多需要二十次比较来确定该元素是否存在。

最快的搜索方式是知道在哪里可以找到你要找的东西。如果你知道一个元素的确切内存位置，那么你就可以直接访问它，而不需要首先进行搜索。将一个元素或（更常见的）它的一个键映射到内存中的元素位置被称为散列。

你可以认为散列不是搜索特定的元素，而是基于元素本身来计算索引。这就是散列函数的工作，它需要持有某些数学属性。一个好的散列函数应该。

接受任意的输入并将其转化为固定大小的输出。 有一个统一的值分布，以减少哈希碰撞。 产生确定性的结果。 是一个单向的函数。 放大输入变化以实现雪崩效应。 同时，它的计算成本不应该太高，否则会得不偿失。散列函数也被用于数据完整性验证以及密码学中。

一个使用这个概念将键值映射成数值的数据结构被称为map、哈希表、字典或关联数组。

注意：Python 有两个内置的数据结构，即 set 和 dict，它们依靠哈希函数来寻找元素。集合对其元素进行散列，而 dict 则对元素键使用散列函数。要想知道dict在Python中是如何实现的，请查看Raymond Hettinger关于现代Python字典的会议演讲。

另一种可视化散列的方法是想象所谓的类似元素的桶，在它们各自的键下分组。例如，你可能会根据颜色把水果收进不同的桶里。

按颜色分组的水果 椰子和一个奇异果进入标有棕色的桶中，而一个苹果最后进入标有红色的桶中，以此类推。这可以让你快速浏览一小部分元素。理想情况下，你希望每个桶里只有一种水果。否则，你会得到所谓的碰撞，从而导致额外的工作。

注意：这些桶以及它们的内容，通常没有特定的顺序。

让我们把IMDb数据集中的名字放到一个字典里，这样每个名字就成了一个键，而相应的值就成了它的索引。

from benchmark import load_names  # Sample code to download
names = load_names('names.txt')
index_by_name = {
    name: index for index, name in enumerate(names)
 }

在将文本名称加载到一个平面列表中后，你可以在一个字典的理解中枚举()它来创建映射。现在，检查元素的存在以及获得它的索引是很直接的。

'Guido van Rossum' in index_by_name
False
'Arnold Schwarzenegger' in index_by_name
True
index_by_name['Arnold Schwarzenegger']
215

由于在幕后使用了哈希函数，你根本就不需要实现任何搜索！这是一个很好的例子。

下面是基于哈希值的搜索算法在IMDb数据集上的表现。

搜索词 元素索引 最佳时间 平均时间 最差时间

Fred Astaire 0 0.18µs 0.4µs 1.9µs
Alicia Monica 4,500,000 0.17µs 0.4µs 2.4µs
Baoyin Liu 9,500,000 0.17µs 0.4µs 2.6µs
missing N/A 0.19µs 0.4µs 1.7µs
缺少 不适用 0.19µs 0.4µs 1.7µs

不仅平均时间比已经很快的二进制搜索Python实现快了一个数量级，而且速度也在所有元素上保持不变，无论它们在哪里。

这一成果的代价是Python进程多消耗了大约0.5GB的内存，加载时间较慢，而且需要保持这些额外的数据与字典内容的一致性。反过来，与列表相比，查找的速度非常快，而更新和插入的速度则稍慢。

字典对其键的另一个约束是，它们必须是可散列的，而且它们的散列值不能随时间变化。你可以在 Python 中通过调用 hash() 来检查一个特定的数据类型是否是可散列的。

>>>
>>> key = ['round', 'juicy']
>>> hash(key)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

可变的集合--如 list、set 和 dict--是不可散列的。在实践中，字典的键应该是不可变的，因为它们的哈希值常常取决于键的某些属性。如果一个易变的集合是可散列的，并且可以作为一个键，那么每次内容改变时它的散列值都会不同。考虑一下，如果一个特定的水果由于成熟而改变了颜色，会发生什么？你会在错误的桶里寻找它!

哈希函数还有许多其他用途。例如，它被用于密码学中，以避免以纯文本形式存储密码，以及用于数据完整性验证。

使用 bisect 模块 Python中的二进制搜索可以使用内置的bisect模块来进行，它也有助于保留列表的排序顺序。它是基于寻找函数根的二分法。这个模块带有六个函数，分为两类。

查找索引 插入元素

bisect() insort()
bisect_left() insort_left()
bisect_right() insort_right()

这些函数允许你找到一个元素的索引或者在正确的位置添加一个新元素。第一行的那些只是bisect_right()和insort_right()的别名，分别。实际上，你要处理的只有四个函数。

注意：在将列表传递给其中一个函数之前，你有责任对它进行排序。如果元素没有被排序，那么你很可能会得到不正确的结果。

闲话少说，让我们看看bisect模块的运行情况。

找到一个元素 要在一个排序的列表中找到一个现有元素的索引，你要用bisect_left()。

import bisect
sorted_fruits = ['apple', 'banana', 'orange', 'plum']
bisect.bisect_left(sorted_fruits, 'banana')
1

输出告诉你，香蕉是列表中的第二个水果，因为它在索引1处被发现。然而，如果一个元素丢失了，那么你还是会得到它的预期位置。

bisect.bisect_left(sorted_fruits, 'apricot')
1
bisect.bisect_left(sorted_fruits, 'watermelon')
4

尽管这些水果还没有出现在列表中，但你可以得到一个把它们放在哪里的想法。例如，杏子应该放在苹果和香蕉之间，而西瓜应该成为最后一个元素。你将通过评估两个条件知道是否找到了一个元素。

索引是否在列表的大小范围内？

该元素的值是否是所需的？

这可以转化为一个通用的函数，用于按值查找元素。

def find_index(elements, value):
    index = bisect.bisect_left(elements, value)
    if index < len(elements) and elements[index] == value:
        return index

当有一个匹配时，该函数将返回相应的元素索引。否则，它将隐含地返回 None。

要按键搜索，你必须维护一个单独的键列表。由于这产生了额外的成本，所以在前面计算键值并尽可能地重复使用它们是值得的。你可以定义一个辅助类，以便能够通过不同的键进行搜索，而不需要引入很多重复的代码。

class SearchBy:
    def __init__(self, key, elements):
        self.elements_by_key = sorted([(key(x), x) for x in elements])
        self.key = [x[0] for x in self.elements_by_key])

键是作为第一个参数传递给 init() 的一个函数。一旦你有了它，你就做了一个键值对的排序列表，以便以后能够从它的键中检索到一个元素。用图元来表示配对，可以保证每个配对中的第一个元素都被排序。在下一步中，你要提取键来制作一个适合于你的二进制搜索 Python 实现的平面列表。

然后是按键查找元素的实际方法。

class SearchBy:
    def __init__(self, key, elements):
        ...

    def find(self, value):
        index = bisect.bisect_left(self.keys, value)
        if index < len(self.keys) and self.keys[index] == value:
            return self.elements_by_key[index][1]

这段代码将排序后的键列表一分为二，以获得一个元素的键的索引。如果这样的键存在，那么它的索引就可以用来从先前计算的键值对列表中获得相应的对。该对中的第二个元素就是所需的值。

注意：这只是一个说明性的例子。你最好使用推荐的配方，这在官方文档中有所提及。

如果你有多个香蕉，那么bisect_left()将返回最左边的实例。

sorted_fruits = [
     'apple',
     'banana', 'banana', 'banana',
     'orange',
     'plum'
... ]
bisect.bisect_left(sorted_fruits, 'banana')
1

可以预见的是，为了得到最右边的香蕉，你需要调用bisect_right()或其bisect()的别名。然而，这两个函数返回的索引离实际的最右边的香蕉还有一段距离，这对于寻找新元素的插入点很有用。

bisect.bisect_right(sorted_fruits, 'banana')
4
bisect.bisect(sorted_fruits, 'banana')
4
sorted_fruits[4]
'orange'

合并代码就可以看到有多少香蕉:

l = bisect.bisect_left(sorted_fruits, 'banana')
r = bisect.bisect_right(sorted_fruits, 'banana')
r - l
3

如果缺少一个元素，那么bisect_left()和bisect_right()都会返回相同的索引，产生零香蕉。

插入一个新元素 bisect模块的另一个实际应用是维护一个已经排序的列表中的元素的顺序。毕竟，你不希望每次插入东西时都要对整个列表进行排序。在大多数情况下，这三个函数都可以互换使用。

import bisect
sorted_fruits = ['apple', 'banana', 'orange']
bisect.insort(sorted_fruits, 'apricot')
bisect.insort_left(sorted_fruits, 'watermelon')
bisect.insort_right(sorted_fruits, 'plum')
sorted_fruits

['apple', 'apricot', 'banana', 'orange', 'plum', 'watermelon']

['苹果', '杏', '香蕉', '橙', '李子', '西瓜']

在你的列表中出现重复的内容之前，你不会看到任何区别。但即使如此，只要这些重复的数值是简单的，它就不会变得明显。在左边增加一个香蕉和在右边增加一个香蕉的效果是一样的。

为了注意到这种差异，你需要一个数据类型，其对象尽管具有相同的值，但却可以有独特的身份。让我们使用 @dataclass 装饰器来定义一个 Person 类型，它是在 Python 3.7 中引入的。

from dataclasses import dataclass, field

@dataclass
class Person:
    name: str
    number: int = field(compare=False)

    def __repr__(self):
        return f'{self.name}({self.number})' 

一个人有一个名字和一个任意的数字分配给它。通过将数字字段从平等性测试中排除，你可以使两个人相等，即使他们的该属性值不同。

p1 = Person('John', 1)
p2 = Person('John', 2)
p1 == p2

另一方面，这两个变量指的是完全独立的实体，这使得你可以对它们进行区分。

>>>
>>> p1 is p2
False
>>> p1
John(1)
>>> p2
John(2)

变量p1和p2确实是不同的对象。

请注意，数据类的实例在默认情况下不具有可比性，这使你无法对它们使用二分法算法。

>>>
>>> alice, bob = Person('Alice', 1), Person('Bob', 1)
>>> alice < bob
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'Person' and 'Person'

Python 不知道给 alice 和 bob 排序，因为它们是一个自定义类的对象。传统上，你会在你的类中实现神奇的方法 .lt()，它代表小于，来告诉解释器如何比较这样的元素。然而，@dataclass装饰器接受了一些可选的布尔标志。其中一个是order，当设置为True时，它将导致自动生成用于比较的神奇方法。

@dataclass(order=True)
class Person:
    ...

>>>
>>> alice < bob
True
>>> bob < alice
False

...

反过来，这允许你比较两个人并决定哪一个在先。

最后，你可以利用名字和数字属性来观察各种函数在哪里插入新的人到列表中。

>>>
>>> sorted_people = [Person('John', 1)]。
>> bisect.insort_left(sorted_people, Person('John', 2))
>> bisect.insort_right(sorted_people, Person('John', 3))
>> sorted_people
[John(2), John(1), John(3)]

名字后面括号里的数字表示插入的顺序。在开始时，只有一个约翰，他得到了数字1。然后，你在左边加上它的复制品，后来又在右边加上一个。

在Python中实现二分搜索 请记住，除非你有充分的理由，否则你可能不应该实现这个算法。你会节省时间，而且不需要重新发明车轮。该库的代码很可能是成熟的，已经在生产环境中被真正的用户测试过，并且有多个贡献者提供的广泛功能。

话虽如此，但有些时候，卷起袖子自己做也是有意义的。你的公司可能有一个政策，由于许可或安全问题而禁止某些开源库。也许由于内存或网络带宽的限制，你无法承担另一个依赖性。最后，自己写代码可能是一个很好的学习工具!

你可以用两种方式实现大多数算法。

迭代式 递归式 然而，这条规则也有例外。一个明显的例子是阿克曼函数，它只能用递归的方式来表达。

在你进一步了解之前，请确保你已经很好地掌握了二进制搜索算法。你可以参考本教程的早期部分，快速复习一下。

迭代 该算法的迭代版本涉及一个循环，它将重复一些步骤，直到满足停止条件。让我们从实现一个函数开始，该函数将按值搜索元素并返回其索引。

def find_index(elements, value): ... 你将在以后重复使用这个函数。

假设所有的元素都被排序了，你可以在序列的两端设置下限和上限的边界。

def find_index(elements, value):
    left, right = 0, len(elements) - 1

现在，你要识别中间的元素，看它是否有想要的值。计算中间的索引可以通过取两个边界的平均值来完成。

def find_index(elements, value):
    left, right = 0, len(elements) - 1
    middle = (left + right) // 2

注意到整数除法是如何帮助处理边界范围内的奇数和偶数元素的，将结果打底。根据你要更新边界和定义停止条件的方式，你也可以使用一个上限函数。

接下来，你可以完成或将序列一分为二，继续在其中一个结果中搜索。

def find_index(elements, value):
    left, right = 0, len(elements) - 1
    middle = (left + right) // 2

    if elements[middle] == value:
        return middle

    if elements[middle] < value:
        left = middle + 1
    elif elements[middle] > value:
        right = middle - 1

如果中间的元素是一个匹配的，那么你就返回它的索引。否则，如果它太小，那么你需要将下边界向上移动。如果它太大，那么你需要将上边界向下移动。

为了继续下去，你必须把大部分的步骤放在一个循环里，当下界超过上界时，循环就会停止。

def find_index(elements, value):
    left, right = 0, len(elements) - 1

    while left <= right:
        middle = (left + right) // 2

        if elements[middle] == value:
            return middle

        if elements[middle] < value:
            left = middle + 1
        elif elements[middle] > value:
            right = middle - 1

换句话说，只要下边界低于或等于上边界，你就想进行迭代。否则，就没有匹配，该函数隐含地返回None。

按键搜索可以归结为看一个对象的属性而不是它的字面价值。例如，一个键可以是一个水果的名称中的字符数。你可以调整find_index()来接受和使用一个键参数。

def find_index(elements, value, key):
    left, right = 0, len(elements) - 1

    while left <= right:
        middle = (left + right) // 2
        middle_element = key(elements[middle])

        if middle_element == value:
            return middle

        if middle_element < value:
            left = middle + 1
        elif middle_element > value:
            right = middle - 1

然而，你还必须记住用你要搜索的同一个键对列表进行排序。

>>>
>>> fruits = ['orange', 'plum', 'watermelon', 'apple']
>>> fruits.sort(key=len)
>>> fruits
['plum', 'apple', 'orange', 'watermelon']
>>> fruits[find_index(fruits, key=len, value=10)]
'watermelon'
>>> print(find_index(fruits, key=len, value=3))
None

在上面的例子中，西瓜被选中是因为它的名字正好是十个字符，而列表中没有任何水果的名字是由三个字母组成的。

这很好，但与此同时，你就失去了按值搜索的能力。为了补救这个问题，你可以给这个键分配一个默认值 "无"，然后检查它是否被给予。然而，在一个更精简的解决方案中，你总是想调用这个键。默认情况下，它将是一个返回元素本身的身份函数。

def identity(element):
    return element

def find_index(elements, value, key=identity):
    ...

另外，你可以用一个匿名的lambda表达式来定义身份函数。

find_index()只回答了一个问题。还有另外两个问题， 即 "它在那里吗？"和 "它是什么？" 为了回答这两个问题， 你可以在它的基础上建立。

def find_index(elements, value, key=lambda x: x):
    ...

find_index() answers only one question. 
There are still two others, which are
“Is it there?” and “What is it?” 
To answer these two, you can build 
on top of it:

def find_index(elements, value, key):
    ...

def contains(elements, value, key=identity):
    return find_index(elements, value, key) is not None

def find(elements, value, key=identity):
    index = find_index(elements, value, key)
    return None if index is None else elements[index]
    

通过这三个函数，你几乎可以知道关于一个元素的一切。然而，你仍然没有在你的实现中解决重复的问题。如果你有一个人的集合，而其中一些人有一个共同的名字或姓氏，会怎么样呢？例如，在这些人中可能有一个史密斯家族或几个叫约翰的人。

people = [
    Person('Bob', 'Williams'),
    Person('John', 'Doe'),
    Person('Paul', 'Brown'),
    Person('Alice', 'Smith'),
    Person('John', 'Smith'),
]

为了给Person类型建模，你可以修改之前定义的一个数据类。

from dataclasses import dataclass

@dataclass(order=True)
class Person:
    name: str
    surname: str

请注意顺序属性的使用，以使自动生成用于通过所有字段比较类的实例的神奇方法。另外，你可能更喜欢利用namedtuple，它有一个更短的语法。

from collections import namedtuple
Person = namedtuple('Person', 'name surname')

这两种定义都很好，可以互换。每个人都有一个名字和一个姓氏属性。为了通过其中一个进行排序和搜索，你可以方便地用内置操作者模块中的attrgetter()来定义关键函数。

>>>
>>> from operator import attrgetter
>>> by_surname = attrgetter('surname')
>>> people.sort(key=by_surname)
>>> people
[Person(name='Paul', surname='Brown'),
 Person(name='John', surname='Doe'),
 Person(name='Alice', surname='Smith'),
 Person(name='John', surname='Smith'),
 Person(name='Bob', surname='Williams')]

注意现在人们是按姓氏升序排序的。有约翰-史密斯和爱丽丝-史密斯，但是二进制搜索史密斯的姓氏目前只给你一个任意的结果。

find(people, key=by_surname, value='Smith')
Person(name='Alice', surname='Smith')

为了模仿前面显示的bisect模块的特征，你可以编写你自己版本的bisect_left()和bisect_right()。在找到重复元素的最左边的实例之前，你要确定是否有这样一个元素。

def find_leftmost_index(elements, value, key=identity):
    index = find_index(elements, value, key)
    if index is not None:
        ...
    return index
    #返回索引

如果已经找到了某个索引，那么你可以向左看，并继续移动，直到你遇到一个具有不同键的元素或者没有更多的元素。

def find_leftmost_index(elements, value, key=identity):
    index = find_index(elements, value, key)
    if index is not None:
        while index >= 0 and key(elements[index]) == value:
            index -= 1
        index += 1
    return index

一旦你越过最左边的元素，你需要将索引向右移动一个位置。

寻找最右边的实例也很相似，但你需要翻转条件。

def find_rightmost_index(elements, value, key=identity):
    index = find_index(elements, value, key)
    if index is not None:
        while index < len(elements) and key(elements[index]) == value:
            index += 1
        index -= 1
    return index

现在你不是向左走，而是向右走，直到列表的末端。使用这两个函数可以找到所有重复项的出现。

def find_all_indices(elements, value, key=identity):
    left = find_leftmost_index(elements, value, key)
    right = find_rightmost_index(elements, value, key)
    if left and right:
        return set(range(left, right + 1))
    return set()

这个函数总是返回一个集合。如果没有找到元素，那么这个集合将是空的。如果元素是唯一的，那么这个集合将只由一个索引组成。否则，集合中会有多个索引。

总结一下，你可以定义更多的抽象函数来完成你的二进制搜索 Python 库。

def find_leftmost(elements, value, key=identity):
    index = find_leftmost_index(elements, value, key)
    return None if index is None else elements[index]

def find_rightmost(elements, value, key=identity):
    index = find_rightmost_index(elements, value, key)
    return None if index is None else elements[index]

def find_all(elements, value, key=identity):
    return {elements[i] for i in find_all_indices(elements, value, key)}

这不仅允许你精确地指出元素在列表中的位置，而且还能检索这些元素。你能够提出非常具体的问题。

它在那里吗？ 它在哪里？ 它是什么？

contains() find_index() find()
find_leftmost_index() find_leftmost()
find_rightmost_index() find_rightmost()
find_all_indices() find_all()

这个二进制搜索Python库的完整代码可以在下面的链接中找到。

获取示例代码。点击这里获得你在本教程中学习Python中二进制搜索时要用到的示例代码。

递归 为了简单起见，你将只考虑contains()的递归版本，它告诉你是否找到了一个元素。

注意：我最喜欢的递归的定义是在关于JavaScript函数式编程的Fun Fun Function系列的一集中给出的。

"递归是指一个函数调用它自己，直到它不调用为止。"

• Mattias Petter Johansson

最直接的方法是采用二进制搜索的迭代版本，并使用切分操作符来切分列表。

def contains(elements, value):
    left, right = 0, len(elements) - 1

    if left <= right:
        middle = (left + right) // 2

        if elements[middle] == value:
            return True

        if elements[middle] < value:
            return contains(elements[middle + 1:], value)
        elif elements[middle] > value:
            return contains(elements[:middle], value)

    return False

与其说是循环，不如说是检查一次条件，有时在一个较小的列表上调用同一个函数。这样做会出什么问题呢？嗯，事实证明，切片会产生元素引用的副本，这可能会产生明显的内存和计算开销。

为了避免复制，你可以重复使用同一个列表，但在必要时向函数传递不同的边界。

def contains(elements, value, left, right):
    if left <= right:
        middle = (left + right) // 2

        if elements[middle] == value:
            return True

        if elements[middle] < value:
            return contains(elements, value, middle + 1, right)
        elif elements[middle] > value:
            return contains(elements, value, left, middle - 1)

    return False

缺点是，每次你想调用该函数时，你必须传递初始边界，确保它们是正确的。

>>>
>>> sorted_fruits = ['apple', 'banana', 'orange', 'plum']
>>> contains(sorted_fruits, 'apple', 0, len(sorted_fruits) - 1)
True

如果你犯了一个错误，那么它就有可能找不到那个元素。你可以通过使用默认的函数参数或者引入一个委托给递归函数的辅助函数来改善这个问题。

def contains(elements, value):
    return recursive(elements, value, 0, len(elements) - 1)

def recursive(elements, value, left, right):
    ...

更进一步，你可能更喜欢将一个函数嵌套在另一个函数中，以隐藏技术细节，并利用外部范围的变量重用的优势。

def contains(elements, value):
    def recursive(left, right):
        if left <= right:
            middle = (left + right) // 2
            if elements[middle] == value:
                return True
            if elements[middle] < value:
                return recursive(middle + 1, right)
            elif elements[middle] > value:
                return recursive(left, middle - 1)
        return False
    return recursive(0, len(elements) - 1)

递归()内部函数可以访问元素和值参数，即使它们被定义在包围的范围内。Python 中变量的生命周期和可见性是由所谓的 LEGB 规则决定的，它告诉解释器按照以下顺序寻找符号。

本地范围 包围作用域 全局范围 内置符号 这允许从嵌套的代码块中访问定义在外层范围的变量。

在迭代和递归实现之间的选择往往是性能考虑、便利性以及个人品味的净结果。然而，递归也有一定的风险，这也是下一节的主题之一。

覆盖棘手的细节 下面是《计算机编程艺术》的作者对实现二进制搜索算法的看法。

"虽然二进制搜索的基本思想比较简单，但细节可能出乎意料地棘手，许多优秀的程序员在头几次尝试时都做错了。"

• 唐纳德-克努斯

如果这还不足以阻止你自己编写算法的想法，那么也许这个会。Java的标准库在二进制搜索的实现中存在一个微妙的错误，这个错误十年来一直没有被发现！但这个错误本身可以追溯到它的根源。但这个错误本身的根源要比这早得多。

注：我曾经在一次技术筛选中成为二进制搜索算法的受害者。当时有几个编码难题需要解决，包括二进制搜索。猜猜我没能完成哪一个？是的。

下面的列表并不详尽，但同时，它没有谈到常见的错误，比如忘记对列表进行排序。

整数溢出 这就是刚才提到的Java bug。如果你还记得，二进制搜索的Python算法检查了一个排序的集合中有界范围的中间元素。但是这个中间元素到底是如何选择的呢？通常情况下，你取下界和上界的平均值来找到中间索引。

middle = (left + right) // 2 这种计算平均数的方法在绝大多数情况下都很好用。然而，一旦元素集合变得足够大，两个边界的总和将不适合整数数据类型。它将会大于整数所允许的最大值。

一些编程语言在这种情况下可能会引发错误，从而立即停止程序执行。不幸的是，情况并不总是这样的。例如，Java会默默地忽略这个问题，让数值翻来覆去，变成一些看似随机的数字。只要结果的数字恰好是负数，你才会知道这个问题，从而抛出一个IndexOutOfBoundsException。

下面是一个在jshell中演示这种行为的例子，它有点像Java的交互式解释器。

jshell> var a = Integer.MAX_VALUE
a ==> 2147483647

jshell> a + 1
$2 ==> -2147483648

一个更安全的方法是先计算偏移量，然后把它加到下边界，来找到中间的索引。

middle = left + (right - left) // 2

即使两个值都是最大值，上面公式中的和也不会是。还有一些方法，但好消息是你不需要担心这些，因为Python不存在整数溢出错误。除了你的内存之外，整数的大小没有上限。

>>>
>>> 2147483647**7
210624582650556372047028295576838759252690170086892944262392971263

然而，有一个问题。当你从库中调用函数时，该代码可能会受到C语言的约束，仍然会导致溢出。在 Python 中有很多基于 C 语言的库。你甚至可以建立你自己的 C 语言扩展模块，或者使用 ctypes 将动态链接的库加载到 Python 中。

堆栈溢出 从理论上讲，堆栈溢出问题可能涉及二进制搜索的递归实现。大多数编程语言对嵌套函数调用的数量都有限制。每次调用都与存储在堆栈中的返回地址有关。在Python中，默认的限制是几千级的这种调用。

>>>
>>> import sys
>>> sys.getrecursionlimit()
3000

这对很多递归函数来说是不够的。然而，由于它的对数性质，Python 中的二进制搜索不太可能需要更多。你需要一个2到3000个元素的集合。那是一个有九百多位数的数字!

尽管如此，如果由于错误而导致停止条件的表述不正确，还是有可能出现无限递归的错误。在这种情况下，无限递归最终会导致堆栈溢出。

注意：堆栈溢出错误在手动内存管理的语言中非常常见。人们经常会用谷歌搜索这些错误，看看别人是否已经有类似的问题，这也是一个流行的程序员问答网站的名字。

你可以暂时解除或减少递归限制来模拟堆栈溢出错误。注意，由于Python运行环境必须调用的函数，有效的限制会更小。

>>>
>>> def countup(limit, n=1):
...     print(n)
...     if n < limit:
...         countup(limit, n + 1)
...
>>> import sys
>>> sys.setrecursionlimit(7)  # Actual limit is 3
>>> countup(10)
1
2
3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in countup
  File "<stdin>", line 4, in countup
  File "<stdin>", line 2, in countup
RecursionError: maximum recursion depth exceeded while calling a Python object

递归错误：调用Python对象时超过了最大递归深度 递归函数在堆栈饱和之前被调用了三次。剩下的四次调用一定是由交互式解释器进行的。如果你在PyCharm或其他Python shell中运行同样的代码，那么你可能得到不同的结果。

重复的元素 你知道在列表中出现重复元素的可能性，你也知道如何处理它们。这只是为了强调，Python 中传统的二进制搜索可能不会产生确定性的结果。根据列表的排序方式或它有多少个元素，你会得到不同的答案。

>>>
>>> from search.binary import *
>>> sorted_fruits = ['apple', 'banana', 'banana', 'orange']
>>> find_index(sorted_fruits, 'banana')
1
>>> sorted_fruits.append('plum')
>>> find_index(sorted_fruits, 'banana')
2

列表上有两个香蕉。起初，对find_index()的调用返回左边的那个。然而，在列表的末尾添加一个完全不相关的元素，使得同样的调用得到一个不同的香蕉。

同样的原则，被称为算法的稳定性，适用于排序算法。有些算法是稳定的，意味着它们不会改变等价元素的相对位置。其他的则不做这样的保证。如果你需要按多个标准对元素进行排序，那么你应该总是从最不重要的键开始，以保持稳定性。

浮点取整 到目前为止，你只搜索了水果或人，但数字呢？它们应该没有什么不同，对吗？让我们用列表理解法制作一个增量为0.1的浮点数字列表。

sorted_numbers = [0.1*i for i in range(1, 4)]

该列表应该包含十分之一、十分之二和十分之三的数字。令人惊讶的是，这三个数字中只有两个能被找到。

>>> from search.binary import contains
>>> contains(sorted_numbers, 0.1)
True
>>> contains(sorted_numbers, 0.2)
True
>>> contains(sorted_numbers, 0.3)
False

这不是一个与Python中二进制搜索严格相关的问题，因为内置的线性搜索与它是一致的。

>>> 0.1 in sorted_numbers
True
>>> 0.2 in sorted_numbers
True
>>> 0.3 in sorted_numbers
False

这甚至不是一个与Python有关的问题，而是与浮点数在计算机内存中的表示方法有关。这是由IEEE 754浮点运算标准定义的。不多说了，有些十进制数在二进制形式下没有有限的表示。由于内存有限，这些数字会被四舍五入，造成浮点取舍错误。

注意：如果你需要最大的精度，那么请远离浮点数字。它们在工程方面是很好的。但是，对于货币操作来说，你不希望四舍五入的错误累积起来。建议将所有的价格和金额缩减到最小的单位，如美分或便士，并将其视为整数。

另外，许多编程语言都支持定点数字，如Python中的小数类型。这使你可以控制何时以及如何进行四舍五入。

如果你确实需要处理浮点数，那么你应该用近似比较来代替精确匹配。让我们考虑两个数值略有不同的变量。

>>>
>>> a = 0.3
>>> b = 0.1 * 3
>>> b
0.30000000000000004
>>> a == b
False

尽管两个值几乎相同，但常规的比较给出了一个否定的结果。幸运的是，Python 提供了一个函数，可以测试两个值是否在某个小范围内接近。

>>> import math
>>> math.isclose(a, b)
True

真 这个邻域，也就是两个值之间的最大距离，如果需要的话，可以进行调整。

math.isclose(a, b, rel_tol=1e-16)

假的 你可以用该函数在Python中进行二进制搜索，方法如下。

import math

def find_index(elements, value):
    left, right = 0, len(elements) - 1

    while left <= right:
        middle = (left + right) // 2

        if math.isclose(elements[middle], value):
            return middle

        if elements[middle] < value:
            left = middle + 1
        elif elements[middle] > value:
            right = middle - 1

另一方面，Python 中二进制搜索的这种实现只针对浮点数字。你不可能用它来搜索其他东西而不出错。

分析二进制搜索的时间-空间复杂度 下面的部分将不包含任何代码和一些数学概念。

在计算中，你可以以增加内存使用为代价来优化几乎任何算法的性能。例如，你看到基于哈希值的IMDb数据集搜索需要额外的0.5GB内存来实现无与伦比的速度。

相反，为了节省带宽，你会在通过网络发送视频流之前对其进行压缩，从而增加了需要完成的工作量。这种现象被称为时空权衡，在评估一个算法的复杂性时很有用。

时间-空间复杂度 计算复杂性是对一个算法需要多少资源来完成其工作的相对衡量。这些资源包括计算时间以及它所使用的内存量。比较各种算法的复杂性可以让你做出明智的决定，在特定情况下哪种算法更好。

注意：不需要分配比其输入数据已经消耗的更多内存的算法被称为原地，或原位算法。这导致了对原始数据的变异，有时可能会产生不需要的副作用。

你看了一些搜索算法和它们对一个大数据集的平均性能。从这些测量结果可以看出，二进制搜索比线性搜索要快。你甚至可以知道是什么因素。

然而，如果你在不同的环境中进行同样的测量，你可能会得到轻微的或完全不同的结果。有一些看不见的因素在起作用，可能在影响你的测试。此外，这种测量并不总是可行的。那么，你怎样才能快速、客观地比较时间的复杂性？

第一步是将算法分解成更小的部分，并找到做得最多的那部分。这很可能是一些经常被调用的基本操作，而且运行的时间始终是一样的。对于搜索算法，这样的操作可能是两个元素的比较。

在确定了这一点之后，你现在可以分析该算法了。为了找到时间复杂度，你要描述执行的基本操作的数量与输入的大小之间的关系。从形式上看，这种关系是一个数学函数。然而，你对寻找其精确的代数公式不感兴趣，而是要估计其总体形状。

有几类众所周知的函数，大多数算法都适合。一旦你把一个算法按照其中一个分类，你就可以把它放在一个标尺上。

时间复杂度的常见类别 常见的时间复杂度类别 这些类别告诉你基本操作的数量是如何随着输入大小的增加而增加的。它们从左到右是

常数 对数 线性 二次方 二次方 指数 因数 这可以给你一个关于你正在考虑的算法的性能的想法。一个恒定的复杂度，无论输入大小，都是最需要的。对数复杂度还是相当不错的，表明使用的是分而治之的技术。在这个尺度上越靠右，算法的复杂性就越差，因为它有更多的工作要做。

当你在谈论时间复杂度时，你通常指的是渐进复杂度，它描述了在非常大的数据集下的行为。这通过消除所有的项和系数来简化函数公式，除了增长速度最快的一项（例如，n的平方）。

然而，单一的函数并不能提供足够的信息来准确比较两种算法。时间复杂度可能因数据量的不同而不同。例如，二进制搜索算法就像一个涡轮增压发动机，在它准备好提供动力之前就会产生压力。另一方面，线性搜索算法从一开始就很快速，但很快就达到了峰值功率，最终输掉了比赛。

线性搜索和二进制搜索的时间复杂度 就速度而言，当集合中有一定数量的元素时，二进制搜索算法开始超越线性搜索。对于较小的集合，线性搜索可能是一个更好的选择。

注意：请注意，同一算法可能有不同的乐观、悲观和平均时间复杂性。例如，在最好的情况下，线性搜索算法将在运行一次比较后，找到第一个索引的元素。

在光谱的另一端，它将不得不把一个参考值与集合中的所有元素进行比较。在实践中，你想知道一个算法的悲观复杂性。

有一些渐进复杂度的数学符号，它们被用来比较算法。到目前为止，最流行的是大O记法。大O记号 大O符号代表了渐进复杂性的最坏情况。虽然这听起来相当吓人，但你不需要知道正式的定义。直观地说，它是对描述复杂性的函数尾部增长速度的一个非常粗略的衡量。你把它念成某物的 "大哦"。

大O记法 这个 "东西 "通常是数据大小的一个函数，或者只是代表常数的数字 "一"。例如，线性搜索算法的时间复杂度为O(n)，而基于哈希的搜索的复杂度为O(1)。

注意：当你说某种算法的复杂度为O(f(n))，其中n是输入数据的大小，那么这意味着函数f(n)是该复杂度的图形的上限。换句话说，当n接近无穷大时，该算法的实际复杂度不会比f(n)乘以某个常数的增长速度快。

在现实生活中，大O符号被不太正式地用作上界和下界。这对于算法的分类和比较是很有用的，而不需要担心确切的函数公式。

二进制搜索的复杂性 你将通过确定最坏情况下的比较次数来估计二进制搜索的渐进时间复杂度--当一个元素被遗漏时--作为输入大小的一个函数。你可以用三种不同的方式来处理这个问题。

表格式 图解法 分析法 表格法是指收集经验数据，将其放在一个表格中，并试图通过目测取样值来猜测公式。

元素的数量 比较的数量 0 0 1 1 2 2 3 2 4 3 5 3 6 3 7 3 8 4 当你增加集合中的元素数量时，比较的数量会增长，但增长的速度比线性函数要慢。这是一个好的算法的表现，它可以随着数据的增加而扩展。

如果这对你没有帮助，你可以试试图形法，它通过画图将采样数据可视化。

二进制搜索的经验数据 数据点似乎与一条曲线重叠，但你没有足够的信息来提供一个结论性的答案。它可能是一个多项式，对于较大的输入，其图形会向上和向下转动。

采取分析的方法，你可以选择一些关系并寻找模式。例如，你可以研究在算法的每一步中，元素的数量是如何缩小的。

元素数的比较

• n 第一步 n/2 第2次n/4 第3次 n/8 ⋮ ⋮ k-th n/2 k 在开始时，你从整个n个元素的集合开始。在第一次比较之后，你只剩下一半的元素。接下来，你有四分之一，以此类推。从这个观察中产生的模式是，在第k次比较之后，有n/2 k个元素。变量k是预期的基本操作的数量。

在所有k次比较之后，将不再有任何元素。然而，当你退一步，也就是k-1，将正好剩下一个元素。这就给了你一个方便的等式。

二进制搜索复杂度的方程式 等式的两边都乘以分母，然后对结果取对数底2，再把剩余的常数移到右边。你刚刚找到了二进制搜索复杂度的公式，它的数量级是O(log(n))。

结论 现在你对二进制搜索算法了如指掌。你可以自己完美地实现它，或者利用 Python 的标准库。掌握了时间-空间复杂性的概念，你就能为给定的情况选择最佳的搜索算法。

现在你可以

使用 bisect 模块在 Python 中进行二进制搜索 在Python中递归地和迭代地实现二进制搜索 识别并修复二进制搜索Python实现中的缺陷 分析二进制搜索算法的时空复杂性 比二进制搜索还要快的搜索 有了这些知识，你将在编程面试中大放异彩! 二进制搜索算法是否是某一特定问题的最佳解决方案，你有工具可以自己搞清楚。你不需要计算机科学学位来做这件事。

你可以在下面的链接中抓取你在本教程中看到的所有代码。

获取样本代码。点击这里获取本教程中学习Python中二进制搜索时要用到的示例代码。

立即观看 本教程有一个由Real Python团队制作的相关视频课程。将它与书面教程一起观看，以加深你的理解。在Python中创建一个二进制搜索