bisect管理有序的序列

Time: 2019-08-02

list.sort() vs. sorted()

最核心的区别是前者就地排序，后者会生成新的可迭代对象。

这两个函数有两个相同的关键字：

• reversed: 设为True则降序
• key: 指定排序的依据，默认是恒等函数，即元素自身。可以指定为key=len, key=str.low等

bisect管理有序序列

一旦有序，就必然可以考虑二分法了。

bisect模块的两个主要函数是：

• bisect
• insort

两个函数都利用二分查找算法，在有序序列中查找或插入元素。

bisect.bisect(haystack, needle)搜索

bisect.bisect(haystack, needle)

查询needle在haystack中的位置下标，注意：

• bisect.bisect()是bisect.bisect_right()的简写
• bisect.bisect_left()在元素相同时，是相同元素出现的第一个位置
• bisect.bisect_right()在元素相同时，是相同元素出现的右边的位置

找到下标后，调用haystack.insert(index, needle)插入元素。

bisect.insort(seq, item)

序列有序时，插入数据依然有序。

END.