我们可以使用 Python 的 bisect 模块高效地将项目插入到已排序的列表中。
但列表必须按升序排序,但情况并非总是如此。
在documentation ,原因解释:
Unlike the sorted() function, it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficient design (successive calls to bisect functions would not “remember” all of the previous key lookups).
但是,当我查看 source code ,我看不到任何似乎在“记住”键查找的内容。
我们可以只添加一个 reversed 参数,并在必要时交换此条件表达式的 then 部分:
if x < a[mid]: hi = mid
else: lo = mid+1
为什么这种设计被认为是低效的?
请您参考如下方法:
文档中所说的是 bisect 函数旨在对同一项目列表反复使用。与其使用函数求值来动态计算键,不如预先计算键并使用它们更有效,特别是因为项目列表和键列表是并行的,所以相同的索引可以用于两者。
至于反转,你可以通过反转键列表来获得相同的效果:
items = [9,7,5,3,1]
keys = list(reversed(items))
index = len(items)-bisect_right(keys,7)
但同样,这只有在您要反复使用相同的 key 进行多次搜索时才有意义。
