0Pricing
Competitive Programming Academy · 课时

bisect_left 与 bisect_right

在有序列表中查找插入位置

bisect_left 与 bisect_right 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

无需样板代码地查找

Python 的 bisect 模块为有序列表提供了经过测试的二分查找。无需手写循环，也就不会有差一错误需要调试。

import bisect

不是布尔值，而是插入位置

bisect 不返回真或假，而是返回一个索引，表示将值插入到哪里才能保持列表有序。这个索引才是它真正强大的地方。

a = [1, 3, 3, 3, 7]

bisect_left 偏向左侧

bisect_left 返回值可以插入的第一个位置。对于重复值，它会落在所有相等元素之前，绝不会落在之后。

bisect.bisect_left(a, 3)  # 1

bisect_right 偏向右侧

bisect_right 返回最后一个相等元素之后的位置。对于重复值，它会落在所有匹配值之后。

bisect.bisect_right(a, 3)  # 4

统计相等元素

将两个位置相减，就能在 O(log n) 时间内统计某个值的重复次数。right 减去 left，恰好就是它出现的次数。

lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo)  # 3

该值存在吗

要检查成员关系，请从 bisect_left 获取 i，并确认a[i] 等于目标值。首先要防止 i 达到列表长度。

i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == x

第一个大于或等于 X 的元素

bisect_left 还可以找到第一个大于或等于 x 的元素。该索引直接指向您要找的下界答案。

i = bisect.bisect_left(a, x)  # first >= x

第一个严格大于 X 的元素

需要第一个严格大于 x 的元素吗？bisect_right 会直接给出该索引，也就是上界对应的位置。

i = bisect.bisect_right(a, x)  # first > x

插入后保持有序

insort 会在一次调用中找到位置并完成插入，同时保持列表有序。当您动态构建有序结构时，它非常方便。

bisect.insort(a, 5)  # a stays sorted

在指定范围内查找

可选的 lo 和 hi 参数可以将查找限制在一个切片中。当您只关注子范围时，这样无需复制数据。

bisect.bisect_left(a, x, 2, 5)

通过辅助列表使用键

bisect 会比较完整元素，因此若要按字段查找，请构建一个只包含这些键的平行列表，然后对该列表使用 bisect。

keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)

快速检查

思考重复值和插入位置。

回顾：精通 Bisect

现在您可以找到插入位置、统计重复值，并在对数时间内定位下界和上界。在手写循环之前，请先考虑 bisect。✨

常见问题解答

「bisect_left 与 bisect_right」课时是免费的吗？

是的 — 「bisect_left 与 bisect_right」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「bisect_left 与 bisect_right」这节课中我会学到什么？

在有序列表中查找插入位置 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。

「bisect_left 与 bisect_right」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 不会出错的经典二分查找
  2. bisect_left 与 bisect_right
  3. 第一个 True：谓词二分查找
  4. 对答案进行二分查找
← 返回 Competitive Programming Academy