如果数组中有数百万个数字，如何找到缺失的数字？

Question

我想得到数百万个数字中第一个缺失的数字。例如，我有一个包含n多个元素的数组。它从 0 开始。在这之间，例如，在 4380 之后，4381 丢失，并以 4382 继续。那么，我怎样才能找到 4381？

我在很多网站上看到过这个问题，包括 SO、Quora 等等。但是，我所能找到的只是一小部分数字。为此，for 循环是最佳选择。但是，当我们的数组中有数百万个数字时，这将无法节省时间和内存。在这种情况下，在考虑时间和内存的情况下可以使用什么来完成它？

注意：元素按升序排列

Answer 1

n因此，当您有一个从 开始的有序元素数组时，0元素的索引和值之间存在明显的相关性（假设不能有重复项）：

index   value
0       0
1       1
2       2
...
100     100

因此，您可以使用二分搜索方法并检查例如 处的元素length / 2。如果该值大于其索引，则下方某处必定存在缺失数字。

index   value
0       0
1       1
2       2
...
100     100
101     102
102     103
...
204     205

在此示例中，如果您检查索引，102您将看到值103，因此在索引0和102之间必须有一个缺失的数字。现在，对子数组重复该算法，0..101直到找到丢失的元素。否则，继续处理另一半。

如果元素不是从 at 开始，0那么很容易在各处添加一个常量值。

如果存在没有缺失数字的数组，您还可以从比较最后一个元素开始，如果该值等于其索引，则立即中止。