张芷铭的个人博客

#Python #bisect #二分查找 #算法

bisect 模块提供二分查找算法，用于在有序序列中快速查找插入位置，时间复杂度 O(log n)。

核心函数

函数说明
bisect_left(a, x)返回 x 应插入的位置（左侧）
bisect_right(a, x)返回 x 应插入的位置（右侧）
bisect(a, x)同 bisect_right
insort_left(a, x)在左侧插入 x
insort_right(a, x)在右侧插入 x
insort(a, x)同 insort_right

查找插入位置

1
2
3
4
5
6
7

from bisect import bisect_left, bisect_right

arr = [1, 3, 3, 5, 7]

bisect_left(arr, 3)   # 1（第一个 3 的位置）
bisect_right(arr, 3)  # 3（最后一个 3 之后）
bisect_left(arr, 4)   # 3（4 应插入的位置）

插入元素

1
2
3
4
5

from bisect import insort

arr = [1, 3, 5, 7]
insort(arr, 4)
print(arr)  # [1, 3, 4, 5, 7]

典型应用

元素存在性检查

1
2
3
4
5
6
7

def binary_search(arr, x):
    i = bisect_left(arr, x)
    return i < len(arr) and arr[i] == x

arr = [1, 3, 5, 7]
binary_search(arr, 5)   # True
binary_search(arr, 4)   # False

区间元素计数

1
2
3
4
5
6

def count_in_range(arr, lo, hi):
    """统计 arr 中 [lo, hi) 范围内的元素个数"""
    return bisect_left(arr, hi) - bisect_left(arr, lo)

arr = [1, 2, 3, 4, 5, 6, 7]
count_in_range(arr, 3, 6)  # 3（元素 3, 4, 5）

最近元素查找

1
2
3
4
5
6
7
8

def find_closest(arr, x):
    i = bisect_left(arr, x)
    if i == 0: return arr[0]
    if i == len(arr): return arr[-1]
    return arr[i] if arr[i] - x < x - arr[i-1] else arr[i-1]

arr = [1, 4, 6, 8]
find_closest(arr, 5)  # 4

前提条件

序列必须有序。bisect 不检查有序性，传入无序序列会得到错误结果。

Comments