当前位置：首页 > news >正文

Python Cookbook-5.9 在排序完毕的序列中寻找元素

news 来源：原创 2025/9/19 9:07:11

任务

你需要寻找序列中的一系列元素。

解决方案

解决方案如果列表L已经是排序完毕的状态，则Python 标准库提供的 bisect 模块可以很容易地检查出元素x是否在L中:

import bisect
x_insert_point = bisect.bisect_right(L,x)
x_is_present = L[x_insert_point-1:x_insert_point] == [x]

讨论

对 Python 来说，在列表L中寻找一个元素x是很简单的任务:要检查元素是否存在，if x in L;要知道x的确切位置，L.index(x)。然而，L的长度为n，这些操作所花费的时间与n成正比，因为它们只是循环地检查每一个元素，看看是否与x相等。其实，如果L是排过序的，我们还可以做得更好。

在完成了排序的序列中寻找元素的最经典算法就是二分搜索，因为每一步它都将查找的范围减半——一般情况下它只需要 log₂n 步即可完成搜索。但当需要多次查找某些元素时，这个问题就很值得仔细探讨了，通过使用一些方法，可以为多次搜索尽量少付出一些开销。在调用 L.sort()之后,一旦你决定用二分搜索在L中查找x,应该马上想到 Python标准库的 bisect 模块。

具体地说，我们需要 bisect.bisect_right函数来保持原列表的排序状态，它将返回一个索引，指示出我们要插人的元素的位置，而且它也不会修改列表，如果列表中已经存在相等的元素了，bisec_tright 将返回拥有相同值的元素右边邻接的索引。因此，在调用bisect.bisect_right(L,x)获得了“插入点”之后，只需立刻检査插入点之前的位置，看看是否已经有一个等于x的元素存在了。

解决方案中计算 x_is_present的方式可能不是那么直观。如果知道L不是空列表，我们还能写得更简单、更直观:

x_is_present = L[x_insert_point-1] == x

不过，这个更简单的方式在对空列表进行索引操作的时候会引发异常。当切片的边界无效时，切片操作比索引操作更加“不严谨”，因为它只是生成了一个空的切片，没有引发任何异常。一般来说，当i是somelist的有效索引时，somelist[i:i+1]是和[somelist[i]]一样的单元素列表，但当索引操作引发 IndexError 异常时，它却是一个空的列表[]。对x_is_present 的计算充分利用了这种重要的特性，避免了处理异常，同时也能以统一的方式对L处理空和非空的情况。另一个可选的方式是:

x_is_present = L and L[x_insert_point - 1] == x

这个方式利用了 and 的短路的行为模式来保护索引操作，避免了使用切片操作。

如果元素是可哈希的(意味着元素可以被用作 dict的键)，如5.12节的做法一样，使用一个辅助的 dict 也是一个可行的方法。不过，若元素是可比较的(comparable，若不可比较，排序是不可能实行的)且不可哈希的(因此字典无法将它们当键用)，本节的这个基于已经排序的列表的方法就可能是唯一可行的方案了。

如果列表已经排序完毕，而且需要查找的元素数目不是非常多，那么大多数情况下，用 bisect 要比构建一个辅助字典快，因为在构建字典上的时间投资无法被大量查找分摊。尤其是在 Python 2.4中，bisect 已经被高度优化，比在Python2.3中的对应版本要快得多。比如，在我的计算机上，用bisect.bisectright在含有10000个元素的列表中查找一个元素，Python 2.4要比 Python 2.3 快约4倍。

任务

解决方案

讨论

相关文章：