我今天碰到了这个问题，并试图寻找一种优于O（N）但无法提出解决方案的解决方案。
通过SO搜索，但找不到此问题。
有没有比O（n）更好的解决方案，或者是无法解决比这个更好的问题？
我最初的想法是二进制搜索，但是再次需要对它进行排序，即> n。我还考虑过将快速排序仅应用于搜索元素可能属于的数组的一半，但同样，我们最初进行n次比较，而仅在以后丢弃另一半。我是对的还是看错了方向的解决方案？
我正在尝试使用c ++解决方案，并且没有javascript的IndexOf（）或C＃Array.find（）或LINQ。
使其平行。将数组划分为多个块，然后并行搜索。复杂度为O（n），但运行时间会少得多。实际上，它与否成正比。您拥有的处理器数量。
您可以在C ++中使用并行模式库
