这是 中描述的问题Programming pearls。我无法理解作者描述的二进制搜索方法。谁能帮忙详细说明一下？谢谢。
编辑：我一般可以理解二进制搜索。我只是不明白如何在这种特殊情况下应用二进制搜索。如何确定丢失的数字是否在某个范围内，以便我们可以选择另一个。英语不是我的母语，这也是我不能很好理解作者的原因之一。所以，请使用简单的英语:)
编辑：谢谢大家的精彩回答和评论！我从解决这个问题中学到的最重要的一课是二进制搜索不仅适用于排序数组！
问问题
5110 次
6 回答
9
此网站上有更多信息。从那里引用：
“根据代表每个整数的 20 位来查看这种二进制搜索是很有帮助的。在算法的第一遍中，我们读取（最多）一百万个输入整数，并将具有前导零位的整数写入一个磁带，然后那些有一个前导位到另一个磁带的那些。这两个磁带之一包含最多 500,000 个整数，所以我们接下来使用该磁带作为当前输入并重复探测过程，但这次是在第二位。如果原始输入磁带包含N个元素，第一遍将读取N个整数，第二遍最多N/2，第三遍最多N/4，以此类推，所以总运行时间与N成正比。可以找到丢失的整数通过在磁带上分类然后扫描，但这需要与 N log N 成正比的时间。”
正如您所看到的，这是二分搜索算法的一种变体：将问题分成两部分，并为其中一个较小的部分解决问题。
于 2009-10-29T09:44:20.090 回答
2
我相信作者的意思是您选择当前整数范围的中点，并准备两个输出文件。当您阅读输入时，中点以上的所有内容都进入一个文件，中点以下的所有内容都进入另一个文件。
完成后，选择较小的文件，然后重复操作，使用 [lower bound, midpoint] 或 (midpoint, upper bound] 作为新范围，直到文件和范围小到可以切换到位图模式（或您的输出文件之一为空）。
达米安
于 2009-10-29T09:35:34.873 回答
2
总体思路是这样的：选择一个整数范围，然后选择该范围内的所有整数。如果整数的数量小于范围的大小，则您知道该范围包含一个或多个缺失的数字。
这也适用于最初的问题，即您如何知道有一些缺失的数字。
于 2009-10-29T09:52:11.527 回答
2
如果您考虑从 1 到 N 范围内的数字；其中一半大于 N/2，一半小于 N/2
大于 N/2 的将 MSB 设置为 1；较小的 MSB = 0。
根据 MSB 对整个集合进行分区，这将为您提供两组：小于 N/2 的数字集和大于 N/2 的数字集
尺寸较小的分区缺少元素。
在下一步中，使用下一个 MSB。
如果较小的集合小于 N/2，则其中一半小于 N/4（第二个 MSB=0），另一半大于 N/4（第二个 MSB=1）
如果较小的集合大于 N/2，则其中一半小于 N/2+N/4（第二个 MSB=0），另一半大于 N/2+N/4（第二个 MSB=1）
每一轮都会将搜索空间减半，仅此而已。
Sum ( N / 2^i ) for 0 <= i < log N gives you O(N)
于 2009-10-29T10:43:53.380 回答
2
这与this question基本相同。同样的方法在这里适用于充足的内存情况以获得 O(N) 复杂度。基本上只是递归地尝试将每个整数放到正确的位置，看看什么没有正确的值。
于 2009-10-29T10:51:27.773 回答
1
嗯，它是关于一个包含所有 40 亿个整数的文件，除了一个！这就是这种情况下的问题。
- 当你沿着整数列表移动时，计算总和。
- 最后，使用公式 N * (N + 1) / 2 计算总和，就好像所有整数都存在一样
- 从您在 (2) 处计算的总和中提取 (1) 处的总和。那是缺少的整数。
示例：假设我们有以下序列：9 3 2 8 4 10 6 1 7（1 到 10，缺少 5 个）。当我们按顺序添加整数时，我们得到 9 + 3 + 2 + 8 + 4 + 10 + 6 + 1 + 7 = 50。从 1 到 10 的所有整数的总和将是 10 * (10 + 1) / 2 = 55 . 因此，缺失的整数是 55 - 50 = 5。QED
于 2009-10-29T09:35:32.267 回答