给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺失一个这样的整数）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？

　　我们从表示每个整数的32位的视角来考虑二分搜索。算法的第一趟（最多）读取40亿个输入整数，并把起始位为0的整数写入一个顺序文件，把起始位为1的整数写入另一个顺序文件。在这两个文件中，有一个文件最多包含20亿个整数，我们接下来将该文件用作当前输入并重复探测过程，但这次探测的是第二个位。如果原始的输入文件包含n个元素，那么第一趟将读取n个整数，第二趟最多读取n/2个整数，第三趟最多读取n/4个整数，以此类推。所以总的运行时间正比于n。通过排序文件并扫描，我们也能够找到缺失的整数，但是这样做会导致运行时间正比于n logn。（本习题是伊利诺伊大学的Ed Reingold给出的一道测试题。）