algorithm - "Programming Pearls"二进制搜索帮助

Question

我似乎无法理解这是如何工作的。

问题:
给定一个最多包含 40 亿个随机顺序的 32 位整数的顺序文件，找到一个不在文件中的 32 位整数(并且必须至少有一个缺失)

答案:
根据表示每个整数的 32 位来查看此二分查找很有帮助。在算法的第一遍中，我们读取(最多)40 亿个输入整数，并将具有前导零位的整数写入一个顺序文件，将具有前导一位的整数写入另一个文件。

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

因此，通过一遍又一遍地拆分文件(二进制搜索)，这实际上如何引导我找到丢失的 32 位整数？

Answer 1

每次通过后，您的下一次通过将位于您编制的两个列表中较小的一个。

在某些时候，您必须遇到一个空列表，这将决定您的号码。例如，我们只使用 3 位数。

000
001
110
100
111

在第一次通过之后我们有

000
001

110
100
111

然后我们查看第一个列表中的第 2 位，因为它小于(或等于)第二个。我们会将它们分成

000
001

empty list

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

我们最终必须有一个缺失列表的原因是因为我们每次都为我们的下一次传递选择较小的列表。