Binary search implementation with actors in scala?

Question

Hi,

So I have such problem in Scala, I need to implement binary search with the help of actors, with no loops and recursion, preferably with concurrency between actors. Of course it has no sense, but the problem is as follows. I think that it will be nice to have one actor-coordinator,which coordinates the work of others. So input data is sorted array and the key for searching. Output - index of a key. Do you have some ideas how it possible to implement?

Thanks in advance.

Answer 1

I'm not sure how you could have concurrency for binary search, as every step of the algorithm needs the result of the last one.

You could do "n-ary" search: Split the array in n parts and let every actor compare the value at the boundaries of the sub-arrays. You don't even have to wait for all answers, as soon as you got the two actors with different comparision result, you could start the next round recursively for the subarray you found.