我就是无法理解这个算法是如何工作的。
问题:
给定一个包含最多40亿个32位整数的顺序文件(乱序),找到一个不在文件中的32位整数(必须至少有一个缺失)
答案:
从代表每个整数的32位中的角度来看,将这个二分查找视为有帮助的。在算法的第一次遍历中,我们读取(最多)四十亿个输入整数,并将带有前导零位的整数写入一个顺序文件,将带有前导一位的整数写入另一个文件。
其中一个文件最多包含20亿个整数,因此我们接下来使用该文件作为当前输入,并在第二位上重复探测过程。
通过一次次地拆分文件(二分查找),这实际上如何引导我找到缺失的32位整数呢?
A
,而不是找到“所有”数字。这就是为什么这种方法有效的原因。 - WuHoUnited