algorithm - 给定范围超过 M 的 N 个数字的排序列表，M>>N 找到或确定给定数字不存在。如果可能的话，恒定时间？

<分区>

Possible Duplicate:
Find existence of number in a sorted list in constant time? (Interview question)

首先，我不确定这是否是一道真正的面试题。我在一个声称这是谷歌面试问题的网站上找到了它。话虽如此，它似乎很有趣，这就是为什么我想把它放在这里。

几乎都在上面。我们得到了一个排序列表，其中包含 N 个数字，范围超过 M，其中 M>>N 并且 N 大到足以跨越多个磁盘。

我们需要在 O(logN) 中查找或确定给定数字不存在。对于较小的数据集(二进制搜索)，这是直截了当的。对于多个磁盘上的数据集，这似乎要困难得多。它还说 O(1) 解决方案有额外的分数。有任何想法吗？

我找到了问题 here .

最佳答案

我相信“比 O(logN) 更快”的解决方案是并行搜索每个磁盘。由于数据已排序，您可以通过查看磁盘的 2 个端点知道我们感兴趣的数字是否在上面。然后我们对这个磁盘进行二分查找，得到一个 O(log(N/D)) 的解决方案，其中 D 是磁盘的数量。

鉴于问题当前的措辞方式，没有恒定时间的解决方案。我只能想象作者在尽可能简短地发布问题时遗漏了一些细节。

关于algorithm - 给定范围超过 M 的 N 个数字的排序列表，M>>N 找到或确定给定数字不存在。如果可能的话，恒定时间？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4474766/

相关文章：

java - QuickSort Java 代码给出错误超过时间限制