Let’s say that there is a simple sequential algorithm that performs a linear search of a unique key in an array:

public class SearchSeq {

  public static int search(int[] a, int key) {
    for (int i = 0; i < a.length; i++) {
      if(a[i] == key)
        return i;
    }
    return -1;
 }


public static void main(String[] args) {

   int[] a = …; // an array with n elements
   int key = …; // the key to be searched within a

   long start = System.currentTimeMillis();

   int pos = search(a, key);

   long stop = System.currentTimeMillis();
   long duration = stop - start;

   if(pos > 0)
     System.out.print("found " + key + " at " + pos); 
   else 
     System.out.print(key + " not found"); 

  System.out.println(" within " + duration + "ms");
 }
}

What will be the most fitting thread model in order to redesign the algorithm to run in parallel?

In my opinion the most fitting thread model would be the Master/Worker because in this way we would divide the array into segmenets and search in parallel inside of each segment for the key. Smaller array size -> faster results.

Edit 17/01/2021: The thread models that I have in mind are:

• Master/Worker
• Producer-Consumer
• Pipes & Filters
• Peer to Peer

What do you think?