假设我有整数的连续范围[0, 1, 2, 4, 6]，其中in 3是第一个“缺失”数字。我需要一种算法来找到第一个“洞”。由于范围非常大（可能包含2^32条目），因此效率很重要。数字范围存储在磁盘上；空间效率也是一个主要问题。
[0, 1, 2, 4, 6]
3
2^32
最佳的时间和空间效率最佳算法是什么？
使用二进制搜索。如果某个数字范围没有孔，那么该范围的结束和开始之间的差值也将是该范围内的条目数。
因此，您可以从整个数字列表开始，然后根据前半部分是否有间隔来切掉前半部分或后半部分。最终，您将到达一个范围，其中两个条目中间有一个孔。
这的时间复杂度是O(log N)。与线性扫描相反，线性扫描的最坏情况是O(N)。
O(log N)
O(N)
