Search for an element in array with threads

Question

I have following homework to do: Implement parallel searching for specified element in array. Use number of threads as a function parameter. Eeach thread checks own array piece size of (ArraySize/NumberOfThreads).

class MyThread extends Thread {

    final int[] SEARCH_TAB;
    final int RANGE_TAB[][];
    final int SEARCH_VALUE;

    static int searchIndex = -1;
    static boolean isWorking = true;

    int whichThread;

    MyThread(int[] searchTab, int[][] rangeTab, int searchValue, int whichThread) {
        SEARCH_TAB = searchTab; 
        RANGE_TAB = rangeTab;
        SEARCH_VALUE = searchValue;
        this.whichThread = whichThread;
    }

    @Override
    public void run() {
        for (int i = RANGE_TAB[whichThread][0]; i < RANGE_TAB[whichThread][1] && isWorking; ++i) {
            synchronized(this) {
                if (SEARCH_TAB[i] == SEARCH_VALUE) {
                    isWorking = false;
                    searchIndex = i;
                }
            }
        }
    }   
}

class Main {    

    private static int[][] range(int n, int p) {
        int[] quantities = new int[p];
        int remainder = n % p;
        int quotient = n/p;
        int i;
        for (i = 0; i < p; ++i) quantities[i] = quotient;
        i = 0;
        while (remainder != 0) {
        --remainder;
        ++quantities[i];
        ++i;
        }

        int[][] tab = new int[p][2];
        tab[0][0] = 0;
        tab[0][1] = quantities[0];
        for (i = 1; i < p; ++i) {
            tab[i][0] = tab[i-1][1];
            tab[i][1] = tab[i][0] + quantities[i];
        }
        return tab;
    }

    private static int search(int[] searchTab, int numberOfThreads, int searchValue) {
        int[][] rangeTab = range(searchTab.length, numberOfThreads);
        Thread[] threads = new Thread[numberOfThreads];
        for ( int i = 0; i < numberOfThreads; ++i) threads[i] = new MyThread(searchTab, rangeTab, searchValue, i);
        for ( int i = 0; i < numberOfThreads; ++i) threads[i].start();
        return MyThread.searchIndex;
    }

    public static void main(String[] args) {
        int[] tab = {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9, 10};
        int value = 5;
        int valueIndex = search(tab, 1, value);
        if (valueIndex == -1) System.out.println("Not found."); 
        else System.out.println(valueIndex);
    }
}

This code generally works but cant't find index when one thread is implemented. By the way my teacher said that my code is too long and complicated any suggestions with that?

I will be grateful for any kind of help.

Answer 1

How about the following code:

public class Searcher implements Runnable {
    private int intToFind;
    private int startIndex;
    private int endIndex;
    private int[] arrayToSearchIn;

    public Searcher(int x, int s, int e, int[] a) {
        intToFind = x;
        startIndex = s;
        endIndex = e;
        arrayToSearchIn = a;
    }

    public void run() {
        for (int i = startIndex; i <= endIndex; i++) {
            if (arrayToSearchIn[i] == intToFind) System.out.println("Found x at index: " + i);
        }
    }
}

public class Starter {
    public static void main(String[] args) {
        int[] a = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
        int numberOfThreads = 5;
        int x = 20;
        findElement(numberOfThreads, x, a);
    }

    private static void findElement(int numberOfThreads, int x, int[] a) {
        int sizeOfa = a.length;
        int range = sizeOfa/numberOfThreads;
        for (int i = 0; i <= numberOfThreads-1; i++) {
            Thread searcher;
            if (i == numberOfThreads-1) {
                searcher = new Thread(new Searcher(x, i*range, sizeOfa-1, a));
            } else {
                searcher = new Thread(new Searcher(x, i*range, i*range+range-1, a));
            }
            searcher.start();
        }
    }
}

You can still optimize the code e.g. by splitting the rest of the array on all threads instead of just pushing it into the last one (like in my code) but the idea is still the same.

EDIT: I think that there is a problem with your code. It will only show one appearance of x in the array. If you are looking for x = 5 in [5,5,5,5,5] using five threads you can neven know which index will be returned because it depends on how your threads are scheduled. The outcome will be between 0 and 5.