"Programming Pearls" 二分查找帮助

Question

我就是无法理解这个算法是如何工作的。

问题：
给定一个包含最多40亿个32位整数的顺序文件（乱序），找到一个不在文件中的32位整数（必须至少有一个缺失）

答案：
从代表每个整数的32位中的角度来看，将这个二分查找视为有帮助的。在算法的第一次遍历中，我们读取（最多）四十亿个输入整数，并将带有前导零位的整数写入一个顺序文件，将带有前导一位的整数写入另一个文件。

其中一个文件最多包含20亿个整数，因此我们接下来使用该文件作为当前输入，并在第二位上重复探测过程。

通过一次次地拆分文件（二分查找），这实际上如何引导我找到缺失的32位整数呢？

- bbbb

Answer 1

在每次排序后，下一次排序将在您编译的两个列表中较小的列表上进行。

在某个时刻，您必须遇到一个空列表，并且这将确定您的数字。例如，让我们使用3位数字。

000
001
110
100
111

第一次通过之后，我们拥有了

000
001

110
100
111

然后我们看第一个列表中的第二位，因为它比第二个列表的数字小于等于第二个列表中的数字。 我们会将它们分成

000
001

empty list

注意以01开头的文件是空的，这意味着没有以01开头的数字，因此010和011缺失。

我们必须最终有一个缺失列表，因为每次选择较小的列表进行下一步操作。

- WuHoUnited

---

101呢？它也应该丢失了吧。 - bbbb

你的问题要求找到一个数字A，而不是找到“所有”数字。这就是为什么这种方法有效的原因。 - WuHoUnited

哦，我明白了，我以为它会输出所有的数字，谢谢！ - bbbb

@WuHoUnited “然后我们看第一个列表中的第二位，因为它比第二个列表中的某个元素小（或相等）”...比哪个第二个元素小或相等？此外，时间复杂度是多少？O(lg n)？ - Geek

@Geek 在那个句子中，第一个列表指的是000、001。（第二个列表将是110、100、111）。我所说的“较小”是指其中元素较少。大O(n)复杂度取决于你想让“n”成为什么（在这种情况下，n是32位还是2^32个可能的数字或者是40亿个选定的数字）。 - WuHoUnited

Answer 2

最终，如果你不断分割，你将拥有（最多）40亿个文件，每个文件中都有一个整数。理论上，你将“知道”哪一个缺失，因为它没有对应的文件。

你可能会遇到一种情况，即整数数量为奇数。在这种情况下，较小的一半将缺少一个数字。这使得定位缺失数字更容易。

在整数数量为偶数的情况下，你知道有两个数字缺失。在这种情况下，你必须找到比各自一半更小的部分，然后按照上述解决方案进行处理。

- Scott M.