Parallel Binary Search

parallel-processing binary-search
user114518 picture user114518 · Dec 8, 2011 · Viewed 13.9k times · Source

I'm just starting to learn about parallel programming, and I'm looking at binary search.

This can't really be optimized by throwing more processors at it right? I know it's supposedly dividing and conquering, but you're really "decreasing and conquering" (from Wikipedia).

Or could you possibly parallelize the comparisons? (if X is less than array[mid], search from low to mid - 1; else if X is greater than array[mid] search from mid + 1 to high, else return mid, the index of X)

Or how about you give half of the array to one processor to do binary search on, and the other half to another? Wouldn't that be wasteful though? Because it's decreasing and conquering rather than simply dividing and conquering? Thoughts?

Answer

Orch picture Orch · Oct 2, 2012

You can easily use parallelism.

For k is less than n processors, split the array into n/k groups and assign a processor to each group.

Run binary search on that group.

Now the time is log(n/k).

There is also a crew method that is logn/log(k+1).

Related questions

How do I parallelize a simple Python loop?

This is probably a trivial question, but how do I parallelize the following loop in python? # setup output lists output1 = list() output2 = list() output3 = list() for j in range(0, 10): # calc individual parameter value parameter = j * offset # call the calculation out1, …

Read More
How to wait for all threads to finish, using ExecutorService?

I need to execute some amount of tasks 4 at a time, something like this: ExecutorService taskExecutor = Executors.newFixedThreadPool(4); while(...) { taskExecutor.execute(new MyTask()); } //...wait for completion somehow How can I get notified once all of them are complete? For now …

Read More
How do you run multiple programs in parallel from a bash script?

I am trying to write a .sh file that runs many programs simultaneously I tried this prog1 prog2 But that runs prog1 then waits until prog1 ends and then starts prog2... So how can I run them in parallel?

Read More