algorithm - 在排序列表中查找第一个 "missing"数字

Question

假设我有整数的连续范围 [0, 1, 2, 4, 6]，其中 3 是第一个“缺失”的数字。我需要一种算法来找到第一个“洞”。由于范围非常大(可能包含 2^32 条目)，效率很重要。数字范围存储在磁盘上；空间效率也是一个主要问题。

最好的时间和空间效率算法是什么？

Answer 1

使用二进制搜索。如果一个数字范围没有空洞，那么该范围的结尾和开头之间的差值也将是该范围内的条目数。

因此，您可以从整个数字列表开始，然后根据前半部分是否有空隙来截断前半部分或后半部分。最终您会看到一个范围，其中有两个条目，中间有一个洞。

这个的时间复杂度是O(log N)。对比线性扫描，其最坏情况是 O(N)。