并行二分查找

Question

我刚刚开始学习并行编程，我正在研究二进制搜索。

这不能通过投入更多的处理器来真正优化它，对吗？我知道这应该是分而治之，但你实际上是在“减少和征服”(来自Wikipedia)。

或者，您可以将这些比较并行化吗？(如果X小于array[mid]，则从low搜索到mid - 1；否则，如果X大于array[mid]，则从mid + 1搜索到high，否则返回X的索引mid )

或者，您可以将数组的一半分配给一个处理器进行二进制搜索，而将另一半分配给另一个处理器？不过，这不是很浪费吗？因为它在减少和征服，而不是简单地划分和征服？有什么想法？

Answer 1

您可以很容易地使用并行性。

对于k小于n的处理器，请将阵列拆分为n/k组，并为每个组分配一个处理器。

在该组上运行二进制搜索。

现在时间是log(n/k)。

还有一个名为logn/log(k+1).的crew方法

Answer 2

我认为它当然有资格并行化。至少，跨两个线程。让一个线程执行深度优先搜索，另一个线程执行广度优先搜索。优胜者是执行速度最快的算法，不同的数据集可能不同。

Answer 3

我在并行编程方面没有太多经验，但我怀疑这是一个很好的并行处理候选者。算法的每一步都依赖于执行一次比较，然后根据该比较沿着一条设置的“路径”前进(您要么找到了自己的值，要么现在必须根据比较在设置的“方向”上进行搜索)。两个单独的线程执行相同的比较不会让您更快，并且单独的线程都需要依靠相同的比较来决定下一步要做什么，所以它们不能真正单独完成任何有用的、划分的工作。

至于你拆分数组的想法，我认为在这种情况下你只是否定了二进制搜索的好处。你的值(假设它在你的数组中)，要么在你数组的上半部分，要么在下半部分。二分查找中的第一个比较(在中点)将告诉您应该查找哪一半。如果更进一步，可以考虑将N个元素的数组分成N个不同的二进制搜索(这是一种简单的并行化尝试)。你现在正在做N个比较，当你不需要的时候。您正在失去二进制搜索的能力，因为每次比较都会将您的搜索范围缩小到适当的子集。

希望这能有所帮助。欢迎评论。