在未排序数组中搜索元素的最快方法 [英] Fastest way to search for an element in unsorted array

问题描述

我今天刚碰到这个问题，正在尝试一种比 O(N) 更好的解决方案，但找不到.

I just bumped on to this question today and was trying for a solution that is better than O(N) but could not come up with one.

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

Searched through SO but couldn't find this question.

是否有比 O(n) 更好的解决方案，或者是无法更好地解决的问题?

Is there any solution better than O(n) or is it a problem that cannot be solved better than that?

我最初的想法是二分搜索，但同样你需要对它进行排序，这又是 >n.我还想过只对搜索元素可能所属的数组的一半应用快速排序，但同样我们最初进行了 n 次比较，然后才丢弃另一半.是我做对了还是看错了方向?

My initial thought was Binary Search but again for that you need to sort it which is again >n. I also thought of applying quicksort for just the half of the array to which the search element might belong but again we are making n comparisons initially and discarding the other half only later. Am I getting this right or am I looking at the solution in a wrong direction?

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

I was trying for a solution in c++ and no javascript's IndexOf() or C# Array.find() or LINQ's.

推荐答案

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

Make it parallel. Divide the array in chunks and search in parallel. The complexity will be O(n) but running time will be much less. Actually it will be proportional to no. of processors you have.

您可以在 C++ 中使用并行模式库

You can use Parallel Patterns Library in C++

这篇关于在未排序数组中搜索元素的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！