Python bisect 的边界查找:重复值计数与有序前提

举报
yd_254857454 发表于 2026/11/11 10:13:58 2026/11/11
【摘要】 用已在免费 DevSpace 运行的五个断言说明 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. 使用前的三个检查

  1. 输入是否已按查询采用的顺序排列,查询期间是否保持稳定?
  2. 需要的是插入边界、是否存在,还是重复值计数?不要直接把插入位置当成命中。
  3. 总成本是否包含排序、插入搬移和对象比较?针对真实数据量再决定是否值得使用。

本文集中验证重复整数、缺失目标和空列表。带 key 的复杂对象查询、NaN、自定义比较器及并发访问不在这次运行验证范围内。进一步阅读可查阅 Python 官方文档中 bisect 模块的 API 和 Performance Notes。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0)

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。