Python bisect 查找重复分数时怎么定位区间

如果有序分数列表里同一个分数出现多次，正确做法不是只取一个二分位置，而是同时计算 bisect_left 和 bisect_right。前者给出重复值的左边界，后者给出排他性的右边界，两个下标直接组成左闭右开区间。

from bisect import bisect_left, bisect_right

# 列表必须有序；两个插入点共同描述目标值的完整范围
left = bisect_left(scores, target)
right = bisect_right(scores, target)
matched = scores[left:right]

matched 是目标分数的全部连续项，出现次数等于 right - left。前提是 scores 已经按升序排列。

官方文档：https://docs.python.org/3/library/bisect.html

两个边界才是完整的区间查找模式

bisect 的函数定位的是“为了保持有序，目标应该插在哪里”，而不是直接返回一个相等元素。对于重复分数，左边界必须放在所有相同值之前，右边界必须放在所有相同值之后，才能表达整段连续数据。

例如列表为 [55, 60, 60, 60, 72]，查找 60 时，左边界是第一个 60 的下标，右边界是最后一个 60 后面的下标。用 Python 切片表示，就是 scores[left:right]。

重复数据出现时，单点查找为什么不够

先准备一个已经排序的分数列表，然后分别调用两个函数。它们都返回插入下标，不会改变原列表。单独使用 bisect_left 只能回答“第一项从哪里开始”，单独使用 bisect_right 只能回答“下一段从哪里开始”，两者缺一就无法安全地切出全部重复项。

from bisect import bisect_left, bisect_right

# 列表必须有序；相同分数会连续排列
scores = [55, 60, 60, 60, 72, 88]
target = 60

# 左边界放在目标值之前，右边界放在目标值之后
left = bisect_left(scores, target)
right = bisect_right(scores, target)
matched = scores[left:right]

print(left, right)
print(matched)
print(right - left)

这段写法得到的区间是 [1, 4)，切片结果是 [60, 60, 60]，出现次数是 3。右端点不参与切片，所以不需要再减一。

把左右边界封装成可复用函数

如果多个业务位置都要查重复分数，可以把两个边界和切片统一封装。返回下标比只返回列表更灵活，调用方还可以计算数量或继续访问原列表。

from bisect import bisect_left, bisect_right

def find_score_range(scores, target):
    # 左右插入点共同描述目标值的左闭右开范围
    left = bisect_left(scores, target)
    right = bisect_right(scores, target)

    # 两个边界相同，说明列表中没有目标值
    if left == right:
        return left, right, []

    # 切片复制出命中的连续分数，不修改原列表
    return left, right, scores[left:right]


scores = [55, 60, 60, 60, 72, 88]
left, right, matched = find_score_range(scores, 60)
print({"left": left, "right": right, "items": matched})

这个函数把“没找到”表示为 left == right，不需要额外遍历列表。若调用方只关心数量，也可以直接使用 right - left，避免创建切片。

无序列表和并发修改是这个模式的反例

目标分数不存在时，两个插入点会落在同一个位置。例如目标是 61，它会插在 60 和 72 之间，左右边界相同，切片自然为空。

from bisect import bisect_left, bisect_right

scores = [55, 60, 60, 60, 72, 88]
target = 61

# 不存在的目标会得到同一个插入点，空切片代表没有匹配项
left = bisect_left(scores, target)
right = bisect_right(scores, target)
print(left, right, scores[left:right])

目标值位于列表首部或尾部时也不需要特殊分支：首部的左边界可以是 0，尾部的右边界可以是 len(scores)。切片协议本身已经覆盖这两种边界。

• 先保证有序：bisect_left 和 bisect_right 不会替你排序；输入无序时，返回值没有区间定位意义。
• 不要把插入点当成命中证明：两个下标相等时，目标值通常不存在；如果需要判断命中，直接看 left != right 即可。
• 右边界是排他下标：区间写成 [left, right)，访问匹配项使用 scores[left:right]，不要写成 right + 1。
• 避免边查边改同一个列表：列表在二分查找期间被其他线程修改，会破坏有序前提；需要并发读写时，应先建立稳定快照或使用更合适的数据结构。

Python 官方文档还特别提醒，二分函数不负责并发安全；如果其他线程在查找期间修改同一个序列，结果可能失去定义。需要并发读写时，应先建立稳定快照，或改用更适合该访问模型的数据结构。

区间结果与字典查找的取舍

如果只是判断一个精确值是否存在，字典或集合通常更直接；bisect 的优势在于已排序数据上的插入位置和连续范围。它表达的是一段有序区间，而不是一次哈希命中。

因此，成绩分布、时间点索引、版本号范围这类数据适合保留排序结构；只做单值存在性判断时，才考虑把数据预先整理成字典或集合。

完整片段：从成绩列表返回重复记录

下面的完整片段保留两个边界，既返回匹配分数，也返回出现次数。调用方可以在需要时只使用下标，不必重复计算。

from bisect import bisect_left, bisect_right


def duplicate_scores(scores, target):
    # scores 必须按升序排列，两个二分函数才能给出有效边界
    left = bisect_left(scores, target)
    right = bisect_right(scores, target)

    # 右边界是排他位置，因此数量直接是差值
    count = right - left
    items = scores[left:right]
    return {"left": left, "right": right, "count": count, "items": items}


scores = [55, 60, 60, 60, 72, 88]
print(duplicate_scores(scores, 60))
print(duplicate_scores(scores, 61))

对于标题中的重复分数问题，核心配方只有两步：left = bisect_left(scores, target)、right = bisect_right(scores, target)。随后使用 scores[left:right] 取出区间，用 right - left 得到数量即可。

使用前的判断清单

• 输入是否已经按与目标一致的规则升序排列？
• 是否同时保留左边界和排他性的右边界？
• 目标不存在时，是否把两个边界相等解释为空区间？
• 只要数量时，是否直接使用 right - left，避免不必要的切片？
• 并发场景中，查找期间是否会有其他线程修改同一序列？

相关问题

为什么不用 list.index 查重复分数？

list.index 只能找到一个匹配位置，而且是线性扫描；左右边界配方可以直接表达连续重复值区间。

目标不存在时需要抛异常吗？

不需要。两个边界相等时返回空切片即可；只有业务明确要求“必须存在”时，才在函数外层主动抛出异常。

重复次数怎么计算最快？

使用 right - left。如果只需要数量，不必创建 scores[left:right] 这个新列表。