本文最后更新于:2024年5月7日 下午
bisect
模块包含两个主要函数,bisect
和insort
,两个函数都利用 二分查找算法来在有序序列中查找或插入元素。
bisect
bisect是 python 的内置模块,主要用来管理已经排序的数据。
bisect搜索
1 |
|
- 在 haystack(干草垛)里搜索 needle(针)的位置,该位置满足的条件是,把 needle 插入这个位置之后,haystack 还能保持升序。
1 |
|
- 也就是在说这个函数返回的位置前面的值,都小于或等于 needle 的值。
- 其中 haystack 必须是一个有序的序列。
1 |
|
bisect.insort 插入新元素
- 当排序数组需要插入元素时,可以先用
bisect(haystack, needle)
查找位置 index,再用haystack.insert(index, needle)
来插入新值。但你也可用bisect.insort
来一步到位,并且后者的速度更快一些。 - 排序很耗时,因此在得到一个有序序列之后,我们最好能够保持它的有 序。
bisect.insort
就是为了这个而存在的,在实现时用的二分搜索的方式查找位置。
1 |
|
参考资料
文章链接:
https://www.zywvvd.com/notes/coding/python/fluent-python/chapter-2/python-bisect/python-bisect/
“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”
微信支付
支付宝支付
Python bisect 管理已排序的序列
https://www.zywvvd.com/notes/coding/python/fluent-python/chapter-2/python-bisect/python-bisect/