编程珍珠：在 40 亿个整数的文件中查找丢失的整数

Question

问题：输入位于顺序文件上。该文件最多包含 40 亿个整数。找出缺失的整数。

根据我的理解解决方案：

1. 制作两个临时文件，一个以 0 开头，另一个以 1 开头

2. 两个必须（4.3B 鸽子和 4B 鸽子）之一的分数必须低于 2B。选择文件并在第二位重复步骤 1 和 2，然后在第三位重复步骤 1 和 2，依此类推。

本次迭代的结束条件是什么？

另外，书中提到算法的效率是 O(n)，但是，

第一次迭代 => n 个探测操作
第二次迭代 => n/2 个探测操作
。
。
。
n + n/2 + n/4 +... 1 => nlogn??

我错过了什么吗？

Answer 1

您将检查这两个文件并选择元素最少的一个。

您将重复该过程，直到完成所有 32 位，最后您将得到一个文件 0 元素。这就是失踪号码之一应该所在的位置。因此，如果您一直在跟踪迄今为止过滤的位，您就会知道该数字应该是多少。

请注意，这是为了找到一个（即“任何”）缺失的数字。如果给定一个由 40 亿个（不是2^32(4294967296)）整数组成的（无序）顺序列表，其中缺少一个整数，而您必须找到其中一个，那么这是行不通的，因为您可以从一开始就截断缺少的整数。

还：

n + n/2 + n/4 + ... 1 <= 2n

不是n log n。

是一个等比数列，a = n, r = 1/2可以用以下公式计算：

n (1-(1/2)^m)
-------------
  1 - (1/2)

因为0 < (1/2)^m < 1对于任何正数m(since 0 < 1/2 < 1)，我们可以说(1-r^m) < 1，因此我们可以说最大值是：

  n.1
-------
1 - 1/2

   n
= ---
  1/2

= 2n