Python bisect 的边界查找:重复值计数与有序前提
从“找到一个值”到“找到一段区间”
在升序列表中查找重复值时,只拿到某一个命中位置往往不够。比如 [1, 2, 2, 2, 4] 中有三个 2,若要统计它们,就需要知道相等元素区间的左边界和右边界。Python 标准库 bisect 提供的正是插入边界,而不是“找到就返回、找不到就报错”的查找接口。
1. 左边界和右边界分别表示什么
对升序整数列表 a 和目标 x:
bisect_left(a, x)返回可将 x 插在已有相等值之前的位置。该位置左侧元素都小于 x。bisect_right(a, x)返回可将 x 插在已有相等值之后的位置。该位置左侧元素都小于或等于 x。
以 a = [1, 2, 2, 2, 4] 为例,目标 2 的左右边界为 1 和 4,因此所有 2 位于左闭右开区间 [1, 4),数量是 4 - 1 = 3。目标 3 不存在时,两条边界都为 4,差值为 0。空列表的两条边界也都是 0。
这说明返回值表示位置,不保证该位置的元素就是目标。边界还可能等于列表长度;没有做范围检查就访问 a[i],可能触发 IndexError。
2. 一个已运行的最小示例
下面的示例只使用标准库和内存数据。它已在华为云免费 DevSpace 体验环境中保存并运行,五个断言全部通过。此处验证的是列出的整数边界样例,不代表做过大规模性能或并发测试。
from bisect import bisect_left, bisect_right
def count_equal(values, target):
return bisect_right(values, target) - bisect_left(values, target)
assert count_equal([], 2) == 0
assert count_equal([1, 2, 2, 2, 4], 2) == 3
assert count_equal([1, 2, 2, 2, 4], 3) == 0
assert bisect_left([1, 2, 2, 2, 4], 2) == 1
assert bisect_right([1, 2, 2, 2, 4], 2) == 4
print("PASS: 5 bisect boundary checks")
运行输出:
PASS: 5 bisect boundary checks
函数名中的 count 并不意味着它适合任意列表。这里必须把“输入已按相同规则排序”作为调用约定写清楚。
3. 有序前提不会被自动检查
二分查找通过比较中间元素来排除一半范围。只有数据有序时,这种排除才成立。bisect 不会先遍历整个列表验证顺序;给它未排序的数据,通常仍会返回一个整数位置,而不是提示输入非法。这个位置不能被解释为正确边界。
如果只是对一个未排序的小列表做一次计数,直接用 values.count(target) 通常更清楚。若同一批数据要被查询很多次,可以先使用 ordered = sorted(values) 生成排序副本,再重复查询。不要忽略首次排序的成本,也不要为了二分查找无意改变原始列表的业务顺序。
需要特别区分“按大小比较的等价区间”和“业务上完全相同”:本文使用普通整数,比较语义一致。对于自定义对象、特殊浮点值或业务去重键,应先明确排序规则及相等规则,不应直接把这个整数例子推广到所有对象。
4. 查找是对数级,插入不一定
在列表已排序、单次元素访问和比较成本可视为常数时,一次边界查找需要 O(log n) 次级别的比较。两个边界相减统计重复值,不需要扫描整个重复段。
但 insort 还要把元素插入 Python 列表,中间插入涉及后续元素移动,整体通常是 O(n)。不能因为用了二分定位,就把整次插入说成 O(log n)。若只查询一次,先排序再二分也未必比直接扫描划算。
列表在查找或插入期间还应保持一致。多个线程同时修改同一个有序列表,可能破坏查找前提;需要在上层协调访问,或查询一个稳定快照。
5. 使用前的三个检查
- 输入是否已按查询采用的顺序排列,查询期间是否保持稳定?
- 需要的是插入边界、是否存在,还是重复值计数?不要直接把插入位置当成命中。
- 总成本是否包含排序、插入搬移和对象比较?针对真实数据量再决定是否值得使用。
本文集中验证重复整数、缺失目标和空列表。带 key 的复杂对象查询、NaN、自定义比较器及并发访问不在这次运行验证范围内。进一步阅读可查阅 Python 官方文档中 bisect 模块的 API 和 Performance Notes。
- 点赞
- 收藏
- 关注作者
评论(0)