我正在为即将来临的面试学习，并且已经多次遇到这个问题（逐字写法）

在N个数字的排序列表中查找或确定数字不存在，其中数字范围超过M，M >> N和N，其大小足以跨越多个磁盘。击败O（log
n）的算法；恒定时间算法的加分。

首先，我不确定这是否是真正的解决方案。我和我的同事已经思考了这个问题好几个星期了，而且看起来似乎病态严重（当然，仅仅因为我们无法想到一种解决方案并不意味着就没有解决方案了）。我会问面试官的几个问题是：

• 排序列表中是否有重复项？
• 与磁盘数量和N有什么关系？

我考虑的一种方法是对每个磁盘的最小值/最大值进行二进制搜索，以确定应该保存该编号的磁盘（如果存在），然后对磁盘本身进行二进制搜索。当然，如果磁盘数量很大并且您还有磁盘的排序列表，那么这仅仅是数量级加速。我认为这将产生某种O（log
log n）时间。

至于M >> N提示，也许如果您知道磁盘上有多少个数字以及范围是多少，则可以使用信鸽原理在某些时候排除某些情况，但我无法弄清楚数量级的提高。

另外，“恒定时间算法的加分点”使我有些怀疑。

关于此问题有任何想法，解决方案或相关历史记录吗？