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

Question

我今天刚碰到这个问题，正在尝试一种比 O(N) 更好的解决方案，但无法想出一个。

通过 SO 搜索但找不到这个问题。

有没有比 O(n) 更好的解决方案，或者是一个无法比它更好解决的问题？

我最初的想法是二分查找，但同样你需要对它进行排序，这又是 >n。我还考虑过仅对搜索元素可能所属的数组的一半应用快速排序，但同样我们最初进行了 n 次比较，稍后才丢弃另一半。我做对了吗？还是我在错误的方向看待解决方案？

我正在尝试使用 C++ 解决方案，但没有使用 JavaScript 的 IndexOf() 或 C# Array.find() 或 LINQ。

Answer 1

使其平行。将数组分成 block 并并行搜索。复杂度为 O(n)，但运行时间会少得多。实际上它会与否成正比。您拥有的处理器数量。

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