Python笔记：bisect库简介

Python笔记：bisect库简介 1. bisect库是什么2. 二分查找操作 1. bisect内置函数说明2. 单纯的二分查找实现方法 3. 插入 & 删除操作 1. 数据的插入2. 数据的删除 4. 参考链接

1. bisect库是什么

今天在做题的时候偶然发现python中有一个强大的内置库，即bisect库，它能够轻易地实现顺序列表中的二分查找与插入操作。

因此，这里，我们就来简单地看一下bisect库使用方法。

它非常地简单，仅包含以下6个函数：

bisect_left(nums, tgt, lo=0, hi=len(nums))bisect_right(nums, tgt, lo=0, hi=len(nums))bisect(nums, tgt, lo=0, hi=len(nums))insort_left(nums, tgt, lo=0, hi=len(nums))insort_right(nums, tgt, lo=0, hi=len(nums))insort(nums, tgt, lo=0, hi=len(nums))

其中，2和3以及5和6本质上来说又是完全相同的（后面我们不会再对其进行区分），因此，事实上bisect库中仅仅包含有4个函数，其中bisect_left()与bisect()用于二分查找，而insort_left()和insort()用于数据的插入。

2. 二分查找操作

二分查找是bisect给出的最核心功能，顾名思义，就是提供了二分查找方法，使得可以在$O(log(N))$时间复杂度的情况下准确地找到元素的目标位置。

1. bisect内置函数说明

我们使用bisect()函数或者bisect_left()函数即可快速地实现顺序列表中任意一个元素的查找。

但是，需要强调的是，bisect提供的查找操作并非是直接找到目标元素的位置，而是找到如果要插入元素，则应当插入的位置。

例如：

from bisect import * nums = [1,2,3] bisect_left(nums, 0) # 0 bisect_left(nums, 1) # 0 bisect_right(nums, 1) # 1 nums = [1,1,1,1] bisect_left(nums, 1) # 0 bisect_right(nums, 1) # 4

用python语言来翻译一下这两个函数的话，应该为：

def bisect_left(nums, tgt, lo=0, hi=len(nums)): if lo >= hi or nums[lo] >= tgt: return lo if nums[hi-1] < tgt: return hi while hi-lo > 1: mid = (hi+lo) // 2 if nums[mid] >= tgt: hi = mid else: lo = mid return lo def bisect_right(nums, tgt, lo=0, hi=len(nums)): if lo >= hi or nums[lo] > tgt: return lo if nums[hi-1] <= tgt: return hi while hi-lo > 1: mid = (hi+lo) // 2 if nums[mid] > tgt: hi = mid else: lo = mid return hi

2. 单纯的二分查找实现方法

由上，如果单纯就是要使用bisect来实现一个二分查找，如果找到则返回idx，否则返回-1的话，正确的实现应该为：

from bisect import * def bi_search(nums, tgt): idx = bisect_left(nums, tgt) if idx == len(nums) or nums[idx] != tgt: return -1 return idx nums = [1,2,3] bi_search(nums, 1) # 0 bi_search(nums, 5) # -1

3. 插入 & 删除操作

基于上述二分查找的结果，我们可以快速地完成有序数列的插入以及删除操作。

不过，如前所述，插入操作事实上bisect库本身已经提供了对应的插入函数。

删除操作虽然没有提供相应的操作，但是我们同样可以快速地进行自定义实现。

1. 数据的插入

bisect库中自带了insort_left()以及insort_right()两个插入函数，他们的实现也非常的trival，分别定义如下：

def insort_left(nums, tgt, lo=0, hi=len(nums)): idx = bisect_left(nums, tgt, lo, hi) nums.insert(idx, tgt) return def insort_right(nums, tgt, lo=0, hi=len(nums)): idx = bisect_right(nums, tgt, lo, hi) nums.insert(idx, tgt) return

因此，我们只需要使用上述两个内置函数，就能轻易地实现顺序列表中数据的顺序插入。

但是，需要注意的是，虽然insort方法在index的检索上的时间复杂度仅为$O(log(N))$，但是插入操作insert的时间复杂度却是$O(N)$的，因此，整体的插入操作的时间复杂度依然还是$O(N)$量级的。

2. 数据的删除

同样地，仿照上述我们自定义实现的数据查找方法，我们同样可以快速给出基于bisect库的数据删除操作。

from bisect import * def bi_delete(nums, tgt): idx = bisect_left(nums, tgt) if idx < len(nums) and nums[idx] == tgt: nums.pop(idx) return nums = [1,1,1] bi_delete(nums, 1) # nums = [1,1]

同样，受限于pop操作的时间复杂度，这一操作的整体时间复杂度还是在$O(N)$量级。

4. 参考链接

https://docs.python.org/3/library/bisect.html