谈谈python二分查找模块

这两天做一道题的时候,需要用到二分查找,印象中Python标准库自带了一个名为bisect的模块,好像可以胜任这个任务。

bisect这个模块有bisect_left()bisect_right()/bisect()insert_left()insert_right()/insert(),这里leftright的区别是遇到相同的元素了,新元素应该插入到左边还是右边,insert非insert的区别在于前者是真的插入新元素,后者只是找到插入的位置。

我们需要做查找操作用bisect_left或者bisect_right,想象一个场景,我们需要从

arr = [0, 1, 2, 3, 3, 5, 6]

这个列表中查第一个3出现的位置,那么可以这样写代码

bisect.bisect_left(arr, 3)

output: 2

这时候它正确的找到第一个出现的3的位置了。要是我们查找一个不存在的元素呢?

bisect.bisect_left(arr, 4)

output: 4

这个时候还是会返回它作为新元素插入应该放置的位置,所以把它当二分查找来用,还得验证该位置对应的元素是否等于被查找的元素

arr[bisect.bisect_left(arr, 4)] == 4

output: False

这样也只会多一次常数操作,所以效率还是比较高的。