如何在Python中实现二分查找算法提高搜索速度_通过bisect模块快速定位-Python教程-PHP中文网

bisect比手写二分更可靠，因其为c实现、经长期验证，且明确区分插入位置（bisect_left/bisect_right）与存在性判断（需索引校验），避免边界错误、越界及重复元素逻辑混乱。

如何在python中实现二分查找算法提高搜索速度_通过bisect模块快速定位

为什么直接用 `bisect` 比手写二分更可靠

手写二分容易在边界条件（比如 left == right 时是否继续循环）、索引越界、重复元素定位逻辑上出错；而 bisect 是 C 实现的，经过长期验证，且明确区分插入位置（bisect_left / bisect_right）和查找存在性（需配合 list[index] == target 判断）。它不返回“是否找到”，只返回位置——这点常被误读。

常见错误现象：bisect.bisect_left(nums, x) 返回 len(nums) 时，说明 x 比所有元素都大；返回索引 i 后不检查 i 就认为找到了，会导致误判。

必须确保输入列表已升序排序，bisect 不校验也不排序
bisect_left 返回第一个 ≥ target 的位置，bisect_right 返回第一个 > target 的位置
对含重复元素的列表，bisect_left 和 bisect_right 的差值就是该元素出现次数

如何用 `bisect` 正确判断元素是否存在

很多人以为 bisect.bisect_left(nums, x) 返回值不是 -1 就代表存在，但该函数**永远不会返回 -1**——它最小返回 0，最大返回 len(nums)。正确做法是先得索引，再做存在性校验。

Li Python Sec Check

Python 安全规范检查工具：基于 CloudBase 规范、腾讯安全指南，LLM 智能分析（默认禁用，优先本地执行）

下载

import bisect
<p>def contains(nums, x):
i = bisect.bisect_left(nums, x)
return i </p><h1>示例</h1><p>nums = [1, 2, 2, 2, 4, 5]
print(contains(nums, 2))  # True
print(contains(nums, 3))  # False
</p>

不要用 if bisect.bisect_left(nums, x) != -1: ——语法合法但逻辑永远为真
如果列表为空，bisect_left([], x) 返回 0，此时 i 为 False，安全
若需频繁查询，且列表不变，可考虑转成 set；但若需找插入点、范围统计或保持顺序，bisect 不可替代

`bisect.insort` 插入时为何比先 append 再 sort 快得多

insort_left 和 insort_right 在 O(n) 时间内完成查找 + 插入，而 lst.append(x); lst.sort() 是 O(n log n)，尤其当列表已较大或需多次插入时，性能差距明显。内部实现是先用二分定位，再用 memmove 移动后续元素。

插入后列表仍保持升序，适合构建动态有序序列（如实时排行榜、滑动窗口中位数）
注意：Python 列表插入中间位置本身是 O(n)，所以 insort 是“最优的 O(n)”，无法降到 O(log n)
若只是偶尔插入、多数时间查找，且能接受离线排序，那先收集再一次性 sorted() 更省事

用 `bisect` 处理自定义对象或复杂 key 的搜索

原生 bisect 只支持可比较类型。若列表是字典、命名元组或类实例，不能直接传入 bisect_left。标准解法是维护一个单独的 key 列表（如所有 item.timestamp），或使用 key 参数（Python 3.10+ 支持）：

# Python 3.10+
from bisect import bisect_left
<p>items = [{'id': 1, 'score': 85}, {'id': 2, 'score': 92}, {'id': 3, 'score': 92}]
keys = [item['score'] for item in items]  # 需手动维护同步</p><h1>或用 key= 参数（推荐，但要求 key 函数稳定）</h1><p>i = bisect_left(items, 92, key=lambda x: x['score'])
</p>