我似乎无法理解这将如何工作。
问题：
给定一个包含最多 40 亿个随机顺序的 32 位整数的顺序文件，找到一个不在文件中的 32 位整数（并且必须至少缺少一个）
回答：
根据表示每个整数的 32 位来查看这种二分搜索会很有帮助。在算法的第一遍中，我们读取（最多）40 亿个输入整数，并将具有前导零位的整数写入一个顺序文件，将前导一位的整数写入另一个文件。
其中一个文件最多包含 20 亿个整数，因此我们接下来使用该文件作为当前输入并重复探测过程，但这次是在第二位。
因此，通过一遍又一遍地拆分文件（二进制搜索），这实际上会如何导致我找到丢失的 32 位整数？
每次通过后，您的下一次通过将在您编译的两个列表中较小的一个。
在某些时候，您必须遇到一个空列表，这将确定您的号码。例如，让我们只使用 3 位数字。
000
001
110
100
111
第一次通过后，我们有
000
001
110
100
111
然后我们查看第一个列表中的第二个位，因为它小于（或等于）第二个。我们会将它们分成
000
001
empty list
注意开头的文件01是空的，这意味着没有以01so开头的数字010并且011丢失了。
我们最终必须有一个缺失列表的原因是因为我们每次都在为下一次传递选择较小的列表。
最终，如果你继续拆分，你将（最多）有 40 亿个文件，每个文件都有一个整数。从理论上讲，您将“知道”缺少哪个文件，因为它没有文件。
您也可能会遇到奇数个整数的情况。在这种情况下，较小的一半将丢失一个数字。这样可以更轻松地找到丢失的号码。
如果你有一个偶数，你就知道少了两个。在这种情况下，您必须找到小于其各自一半的部分，然后继续执行上述解决方案。