基于bisect_left与bisect_right的有序列表元素查询方案评估

可靠性层面 #

• 完全靠谱：bisect是Python官方标准库的模块，bisect_left和bisect_right的实现经过大量测试，对有序列表里的重复元素定位精准。
• 逻辑没毛病：bisect_left找的是第一个不小于目标元素的位置，bisect_right找的是第一个大于目标元素的位置，两者的差值就是目标元素的总数，差值为0就说明元素不存在——这个逻辑不管是数值、字符串还是其他可比较的有序类型都能正确工作。
• 边界情况全覆盖：不管目标元素在列表开头、结尾，整个列表全是该元素，或者元素压根不在列表里，bisect的方法都能给出正确结果。

速度层面 #

• 效率拉满：bisect的两个方法都是**O(log n)**的时间复杂度，10k元素的话，log₂(10000)也就14左右，只需要十几次比较就能搞定，比从头遍历整个列表的O(n)快太多，百万级的列表也能秒出结果，完全适配大型列表的需求。
• 无多余开销：你的函数里除了调用两个bisect方法、算个差值，没别的冗余操作，性能损耗可以忽略不计。

小建议（可选） #

如果你的场景需要直接拿到结束位置（而不是元素数量），可以把返回值改成indexL, indexR - 1（前提是nItem>0），不过当前函数的设计已经完全满足你的需求，看实际使用调整就行。

内容的提问来源于stack exchange，提问作者HotFuzz