如何在Python中通过bisect模块实现高效的二分查找？-Python教程-PHP中文网

bisect.bisect_left仅返回首个≥target的索引，不保证该位置元素等于target，故需校验索引不越界且arr[i]==target。

如何在python中通过bisect模块实现高效的二分查找？

Python 的 bisect 模块本身不提供“查找目标值是否存在”的直接函数，它只负责在已排序列表中定位插入位置；想查是否找到，得自己多写一行比较。

为什么 `bisect.bisect_left` 返回的位置要手动校验？

因为 bisect_left 只保证返回“第一个 >= target 的索引”，但不保证该位置上真有 target。比如对 [1, 3, 5] 查 4，它返回 2（即 5 的位置），但 5 != 4。

正确做法是：先用 bisect_left 得到索引，再判断索引是否越界、且对应元素是否等于目标值：

python-pro

高级 Python 特性、异步编程、性能调优、静态类型、内存管理、Python 内部机制及生态库方面的专家。

下载

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

必须检查 i ，否则查比最大值还大的数会触发 <code>IndexError
不能只靠 bisect_left 返回值非负就认为找到了——它永远返回合法索引（包括 len(arr)）
用 bisect_right 也可以，但需对比 arr[i-1]，逻辑更绕，不推荐

`bisect.insort` 看似方便，但频繁调用会让插入变成 O(n²)

很多人以为 bisect.insort_left(arr, x) 是“高效插入”，其实它只是把二分找位置 + 列表插入两步封装了。而 Python 列表的 insert() 是 O(n) 的，每次都要搬移后续元素。

如果需要动态维护有序序列并高频插入，改用 sortedcontainers.SortedList（第三方）或 heapq（仅支持堆序，不支持任意位置查）
若只是初始化一次、后续只读，用 sorted() 配合 bisect 查找，性能最稳
别在循环里反复 insort —— 10⁴ 次插入可能比先拼列表再 sorted() 慢一个数量级

用 `bisect` 处理带 key 的场景时，得自己维护映射

原生 bisect 不支持 key 参数（不像 sorted(key=...)）。比如按字典的 "score" 字段二分查找，不能直接传 key=lambda x: x["score"]。

常见解法：预提取 key 值为独立列表，如 scores = [d["score"] for d in data]，再对 scores 调用 bisect，用返回索引去原列表取数据
注意保持 scores 和 data 索引严格对齐；如果 data 会动态增删，这套映射就容易出错
更健壮的做法：用 data.sort(key=lambda x: x["score"]) 排序后，再维护一个单独的 score_keys = [d["score"] for d in data]，只对后者查