【python】bisect模块-二分查找算法

一、简介

bisect模块就是基于二分实现的，二分查找要求列表是有序的，bisect实现了在一个有序列表中插入元素并保持列表为有序状态、或返回插入位置但并不进行实际的插入。

二、方法介绍

>>> import bisect
>>> dir(bisect)
['__builtins__', '__cached__', '__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'bisect', 'bisect_left', 'bisect_right', 'insort', 'insort_left', 'insort_right']

2.1、bisect_left /bisect_right不会插入，只返回将会插入的位置索引

bisect_left 和 bisect_right 函数，用入处理将会插入重复数值的情况，返回将会插入的位置。

bisect_left(seq, x) x存在时返回x左侧的位置；
bisect_right(seq, x) x存在时返回x右侧的位置；

>>> a=[0,4,8,11,25]
>>> bisect.bisect_left(a,8)
2
>>> bisect.bisect_right(a,8)
3
>>> a
[0, 4, 8, 11, 25]
>>> 

2.2、insort_left / insort_right插入

insort_left 和 insort_right 会进行实际的插入。

insort_left(seq, x) x存在时插入在左侧插入；
insort_right(seq, x) x存在时在右侧插入；

>>> a
[0, 4, 8, 11, 25]
>>> bisect.insort_left(a,4)
>>> bisect.insort_right(a,7)
>>> a
[0, 4, 4, 7, 8, 11, 25]

题目练习

剑指 Offer II 042. 最近请求次数