折半搜索
通过拆分搜索空间将指数级复杂度减半
折半搜索 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
暴力搜索太慢时
有些问题的 N 约为 40，此时尝试全部 2^N 个子集是无法承受的。折半搜索可以解决这些中等规模的情况。🤝
核心思想
将输入分成两个部分。分别对两个部分进行暴力搜索，然后巧妙地合并两个部分的结果。
将指数减半
两个大小为 N/2 的部分各自只需付出 2^(N/2) 的代价，而不是总共付出 2^N。这个平方根级别的缩减能把 2^40 变成易于处理的 2^20。
经典目标：子集和
询问是否存在某个子集，其和等于目标值 T。N 接近 40 时，子集和是折半搜索的经典问题。
枚举前一半
列出左半部分的每一个子集和并保存下来。有 N/2 个项目时，这只是 2^(N/2) 个和。
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []枚举后一半
对右半部分执行相同操作，构建其完整的子集和列表。现在您有了两个易于处理的列表。
通过查找进行合并
对于每个右侧的和 r，您需要一个等于T 减去 r的左侧和。使用集合或排序后的列表可以快速完成检查。
need = T - r
found = need in left_set两种匹配方式
对于精确目标，请使用哈希集合。对于计数或寻找最接近的和，请将一半排序，然后对其进行二分查找。
时间代价
总工作量约为 2^(N/2) 乘以搜索或排序所需的对数因子。这种复杂度正是 N 接近 40 时问题仍可处理的原因。
内存是需要权衡的因素
您需要存储完整的一半数据，因此内存会增长到 2^(N/2)。只保留必要的数据，以确保不超过限制。
其他应用场景
除了子集和，还可以将它用于容量限制下的最大子集、统计数对，以及离散对数类问题。它特别适合进行清晰的划分。
快速检查
您将折半搜索应用于一个包含 N 个项目的子集问题。大致的时间代价是多少？
回顾
将问题分成两个部分，分别进行暴力搜索，然后匹配左右两侧的和。您只付出了一点内存代价，却获得了巨大的速度提升。🚀
常见问题解答
「折半搜索」课时是免费的吗？
是的 — 「折半搜索」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「折半搜索」这节课中我会学到什么？
通过拆分搜索空间将指数级复杂度减半 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「折半搜索」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。