Binary Search using multithreading

Question

I want to make a program in Java to do a binary search in an array taken dynamically,by using multithreading.So how do I start with the program?

Answer 1

Binary search is not suitable for multi-threading / parallelisation. There is (almost) no potential for parallel speedup.

OTOH ... if you simply want to know how to do concurrent binary search of a sorted array of elements, then provided that:

• none of the searching threads modify the array, AND
• the array is safely published (with respect to the searching threads),

regular binary search by multiple threads will be thread-safe.

Answer 2

Rather than trying to make the search itself multithreaded, it would probably more rewarding to make the calling mechanism be multithreaded and do multiple searches at the same time. Depending on what you are doing, you might get this for free from your Java container (e.g. each HTTP request to a Servlet gets it's own thread already, so you don't have to do anything additional).

Besides: "Premature optimization is the root of all evil" - Donald Knuth

To start, I'd suggest keeping it simple and follow an example like what's shown here: http://en.wikipedia.org/wiki/Binary_search_algorithm And then figure out what you are trying to optimize, if anything at all, and continue as appropriate.