掌握Bisect二分查找算法在实际项目中的高效应用

先看效果，再看代码

上周做商品价格区间筛选功能，用户拖动滑块选最低价和最高价，然后从几千条商品里快速找出匹配的。一开始我用 filter() 暴力遍历，结果卡得不行。后来同事提醒：你这数据是排好序的，直接二分查找啊！

对哦，我怎么忘了 bisect 这个神器。Python 标准库里的 bisect 模块专治这类问题，亲测有效，性能直接起飞。下面这段代码就是我改完后跑通的核心逻辑：

import bisect

# 假设 prices 是已排序的商品价格列表
prices = [10, 25, 30, 45, 50, 60, 75, 80, 90, 100]

# 用户选的区间 [35, 70]
low, high = 35, 70

# 找左边界：第一个 >=35 的位置
left_idx = bisect.bisect_left(prices, low)

# 找右边界：第一个 >70 的位置（注意是 bisect_right）
right_idx = bisect.bisect_right(prices, high)

# 匹配的价格区间
matched_prices = prices[left_idx:right_idx]
print(matched_prices)  # 输出: [45, 50, 60]

就这几行，搞定。比原来快了几十倍，尤其在数据量大的时候优势明显。

这个场景最好用

除了价格筛选，bisect 在这些场景我都用过，效果拔群：

• 时间轴事件定位：比如日志按时间排序，找某个时间点前后的记录
• 分数段排名：考试成绩排序后，快速查某分数段有多少人
• 动态插入保持有序：实时接收数据并插入到已排序列表中，不用每次重新排序

举个动态插入的例子，这是我之前做实时监控面板时用的：

import bisect

# 已排序的响应时间列表
response_times = [120, 150, 200, 250, 300]

# 新来一个响应时间 180ms
new_time = 180

# 找到插入位置，保持列表有序
pos = bisect.bisect_left(response_times, new_time)
response_times.insert(pos, new_time)

print(response_times)  # [120, 150, 180, 200, 250, 300]

比每次 append() 再 sort() 省事多了，尤其高频插入时性能差距巨大。

踩坑提醒：这三点一定注意

别看 bisect 简单，我踩过不少坑，这里重点说三个：

第一，列表必须已排序。这是前提，但新手容易忽略。如果你传了个乱序列表进去，结果完全不可预测。我有次调试半天，最后发现是上游数据没排序，血泪教训。

第二，bisect_left 和 bisect_right 别混用。它们的区别在于处理重复值：

• bisect_left 返回第一个 >= target 的位置
• bisect_right 返回第一个 > target 的位置

比如列表是 [10, 20, 20, 20, 30]，找 20：

bisect.bisect_left([10,20,20,20,30], 20)   # 返回 1
  bisect.bisect_right([10,20,20,20,30], 20)  # 返回 4

如果你要找所有等于 20 的元素，用 left 和 right 的差值就是数量。搞反了就漏数据。

第三，别用它查未排序数据。有人觉得“二分查找快”，不管三七二十一就上。但如果你的数据是乱的，先排序的成本可能比暴力遍历还高。记住：只在**已排序**且**频繁查询**的场景用它。

高级技巧：自定义比较逻辑

标准 bisect 只能处理简单数值或字符串，但实际项目中经常要查对象。比如商品列表是字典，按价格排序，但你想根据价格查。这时候可以用 key 参数（Python 3.10+ 支持）：

import bisect

# 商品列表，按 price 排序
products = [
    {'name': 'A', 'price': 10},
    {'name': 'B', 'price': 25},
    {'name': 'C', 'price': 30},
    {'name': 'D', 'price': 45}
]

# 提取价格作为 key
prices = [p['price'] for p in products]

# 查找价格 >=30 的第一个商品
target_price = 30
idx = bisect.bisect_left(prices, target_price)
if idx < len(products):
    print(products[idx])  # {'name': 'C', 'price': 30}

如果版本低于 3.10，没有 key 参数，就得手动维护一个平行的 key 列表（像上面这样），或者自己写二分函数。我自己封装过一个通用版本，支持传入 key 函数：

def bisect_left_custom(arr, target, key_func):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if key_func(arr[mid]) < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

# 使用示例
idx = bisect_left_custom(products, 30, lambda x: x['price'])

虽然麻烦点，但灵活性高。建议直接用这种方式，比每次拆列表省事。

别被名字吓到，bisect 就是二分查找的封装

其实 bisect 本质就是二分查找算法的标准库实现，名字来源于“bisect”（平分）。它把常见的二分操作（找插入点、找边界）封装好了，不用你手写 while 循环。核心就两个函数：bisect_left 和 bisect_right，其他像 insort_left 都是它们的变种。

我以前也手写过二分，边界条件调到怀疑人生。现在直接用 bisect，省心又可靠。官方文档说它的时间复杂度是 O(log n)，实测在 10w 条数据下，查询基本是微秒级，比线性查找快几个数量级。

最后的小建议

如果你在做前端，可能会想“这不就是 JS 的 Array.findIndex 吗”？但注意，JS 原生没有二分查找方法，得自己实现或用 Lodash。而 Python 的 bisect 是内置的，开箱即用，这点很爽。

另外，别一上来就优化。如果数据量小（比如几百条），暴力遍历完全够用。只有当你发现性能瓶颈，且数据是有序的，再考虑 bisect。过早优化是万恶之源，但该用的时候别犹豫。

以上是我踩坑后的总结，希望对你有帮助。这个技巧的拓展用法还有很多，比如结合堆（heapq）做优先队列，后续会继续分享这类博客。有更优的实现方式欢迎评论区交流！