搜索未排序数组中元素的最快方法

Question

我今天刚刚提出了这个问题,并且正在尝试一种比O(N)更好的解决方案,但却找不到一个.

通过SO搜索但无法找到这个问题.

有没有比O(n)更好的解决方案,还是一个无法解决的问题呢？

我最初的想法是二进制搜索,但是你需要再次对它进行排序> n.我还考虑过将quicksort应用于搜索元素可能属于的数组的一半,但我们再次进行n次比较,之后才丢弃另一半.我是正确的还是我在错误的方向上看待解决方案？

我正在尝试用c ++解决方案而没有javascript的IndexOf()或C#Array.find()或LINQ.

Answer 1

让它平行.将数组划分为块并并行搜索.复杂性将是O(n),但运行时间会少得多.实际上它与否成正比.你有的处理器.

您可以在C++中使用Parallel Patterns Library

Answer 2

你是对的,最快的方法是简单地遍历数组并寻找它.没有进一步的信息,你无能为力.

除非你有量子计算机,否则就是这样.

Answer 3

如果您只搜索一个元素，只需遍历它即可。没有办法让它更快。

如果您要搜索多次，则值得对其进行索引（或排序，如果您愿意）并快速进行以下搜索 (log(n))。