0Pricing
Competitive Programming Academy · 课时

第一个 True：谓词二分查找

搜索单调的是或否边界

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

搜索真假边界

许多问题都隐藏着一个单调谓词：先是假、再一直为真。即使没有有序数组，二分查找也能找到第一个为真的位置。

# FFFFTTTT  -> find first T

什么是单调

当一个谓词一旦变为真就始终为真时，它就是单调的。正是这一条性质让您能够用二分查找边界。

def ok(x):
    return x * x >= target

确定答案空间

选择一个肯定包含边界的范围。将 low 设为最小候选值，将 high 设为一个肯定使 ok 为真的值。

low, high = 0, 10**9

测试中点

取 mid 并调用 ok(mid)。布尔结果会告诉您应保留哪一半，这与普通二分查找中比较值的方式完全相同。

mid = (low + high) // 2
if ok(mid):
    ...

为真意味着可能更小

如果 ok(mid) 为真，mid 是一个有效答案，但更小的值也可能可行。请设置 high = mid，而不是 mid - 1，以保留 mid。

if ok(mid):
    high = mid

为假意味着向更高处查找

如果 ok(mid) 为假，边界位于 mid 上方。使用 low = mid + 1，舍弃 mid 及其以下的所有值。

else:
    low = mid + 1

当 Low 小于 High 时循环

请使用 while low < high，而不是小于或等于。两个指针会汇聚到第一个为真的索引，然后循环停止。

while low < high:
    mid = (low + high) // 2

答案就是 Low

循环结束时，low 等于 high，两者都指向第一个为真的值。返回 low，作为您要找的边界。

return low  # first x where ok(x)

为什么 high = mid 有效

由于 mid 可能就是答案，因此不能跳过它。使用 high = mid 会在缩小范围的同时保留 mid，从而保证取得进展。

high = mid  # mid stays a candidate

整数平方根示例

要找到满足 x*x 至多为 n 的最大 x，请搜索 x*x > n 的第一个为真位置，然后回退一位。这个模式可以反复复用。

def ok(x):
    return x * x > n
# answer is found_index - 1

一个模板解决许多问题

这个首个为真模板可以解决无数任务：最小可行值、最左索引、最小容量。掌握一次，就能到处复用。

# low<high, ok->high=mid, else low=mid+1

快速检查

确定哪个移动会让候选值继续保留。

回顾：找到首个为真

现在您可以将问题转化为单调谓词，并用二分查找边界。high = mid 加上 while low < high，就是安全的模式。🧭

常见问题解答

「第一个 True：谓词二分查找」课时是免费的吗？

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

「第一个 True：谓词二分查找」这节课中我会学到什么？

搜索单调的是或否边界 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

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

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

「第一个 True：谓词二分查找」课时需要多长时间？

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

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

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

此课程中的所有课时

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