Python 内置模块bisect的使用方法

74 阅读 0 评论 49 点赞

我是靠谱客的博主痴情手套，最近开发中收集的这篇文章主要介绍Python 内置模块bisect的使用方法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

bisect — 数组二分查找算法

因为其使用了基本的二分（bisection）算法, 使得他们可以在插入新数据仍然保持有序

查找： bisect(array, item)
插入： insort(array,item）

定义了以下函数：
bisect.bisect_left(a, x, lo=0, hi=len(a))
在 a 中找到 x 合适的插入点以维持有序。参数 lo 和 hi 可以被用于确定需要考虑的子集；默认情况下整个列表都会被使用。如果 x 已经在 a 里存在，那么插入点会在已存在元素之前（也就是左边）。如果 a 是列表（list）的话，返回值是可以被放在 list.insert() 的第一个参数的。

返回的插入点 i 可以将数组 a 分成两部分。左侧是 all(val < x for val in a[lo:i]) ，右侧是 all(val >= x for val in a[i:hi]) 。

bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))
类似于 bisect_left()，但是返回的插入点是 a 中已存在元素 x 的右侧。

返回的插入点 i 可以将数组 a 分成两部分。左侧是 all(val <= x for val in a[lo:i])，右侧是 all(val > x for val in a[i:hi]) for the right side。

bisect.insort_left(a, x, lo=0, hi=len(a))
将 x 插入到一个有序序列 a 里，并维持其有序。如果 a 有序的话，这相当于 a.insert(bisect.bisect_left(a, x, lo, hi), x)。要注意搜索是 O(log n) 的，插入却是 O(n) 的。

bisect.insort_right(a, x, lo=0, hi=len(a))
bisect.insort(a, x, lo=0, hi=len(a))
类似于 insort_left()，但是把 x 插入到 a 中已存在元素 x 的右侧。

import bisect
matrix = [2,5,8,12,19]
target = 5
print(bisect.bisect(matrix, target))
#2
print(bisect.bisect_left(matrix, target)) #1
print(bisect.bisect_right(matrix, target)) #2

import bisect
matrix = [2,5,8,12,19]
target = 3
bisect.insort(matrix, 3)
print(matrix)
# [2, 3, 5, 8, 12, 19]
bisect.insort_right(matrix, target)
print(matrix)
# [2, 3, 5, 8, 12, 19]
bisect.insort_left(matrix, target)
print(matrix)
# [2, 3, 5, 8, 12, 19]

附 LeetCode
240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

二分查找题解：

class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for row in matrix:
idx = bisect.bisect_left(row, target)
if idx < len(row) and row[idx] == target:
return True
return False