Multi-threaded Java program for Linear Search

Are you looking to perform Linear Search optimally in Java for large arrays?

You have come to the right article. In this article at OpenGenus, we harness the power of multi-threaded to run Linear Search on an array in parallel across multiple threads in Java. We use threads to divide the array into smaller parts and perform Linear Search on each part concurrently.

Whether or not you are a Java developer, this article is a must read.

Table of contents:

1. Approach for Multi-threaded Linear Search
2. Multi-threaded Java program for Linear Search
3. Compile and Run

Approach for Multi-threaded Linear Search

The main approach is as follows:

• Let us say we want to use M threads and there are N elements to search form. N >= M.
• We divide the array of N elements into M chunks. Each chunk has N/M elements.
• M threads are created and each thread is assigned to perform Linear Search on separate chunk.
• At the end, the results are combined. If an thread returns a non-negative number, the returned value is adjusted to reflect the index in the original array and returned as the final output. If all return values are -1, then -1 is returned.

In Java:

• We create an ArrayList of threads.

List<Thread> threads = new ArrayList<>();

• We create a new thread for each chunk.

Thread t = new Thread(() -> { /* ... */ });

• Each thread deals with a different chunk of the array which is denoted by start and end. Note interrupt() method is used when a match occurs to stop all threads and return the answer. This is an important optimization.

for (int j = start; j < end; j++) {
    if (arr[j] == x) {
        Thread.currentThread().interrupt();
        return j;
    }
}

• We wait for all threads to complete using the join method. If all threads complete execution and no value is returned, then -1 is returned to denote that the target value is not present in the array.

for (Thread t : threads) {
    t.join();
}

Multi-threaded Java program for Linear Search

Following is the complete Java program to do Linear Search in multi-threaded way:

// Part of iq.opengenus.org
import java.util.ArrayList;
import java.util.List;

public class ParallelLinearSearch {

    // Perform linear search in parallel
    public static int parallelLinearSearch(int[] arr, int x, int numThreads) {
        int n = arr.length;
        int chunkSize = n / numThreads;

        List<Thread> threads = new ArrayList<>();

        // Create threads and search through different chunks of the array
        for (int i = 0; i < numThreads; i++) {
            int finalI = i;
            Thread t = new Thread(() -> {
                int start = finalI * chunkSize;
                int end = (finalI == numThreads - 1) ? n : (finalI + 1) * chunkSize;

                for (int j = start; j < end; j++) {
                    if (arr[j] == x) {
                        Thread.currentThread().interrupt();
                        return j;
                    }
                }
            });
            threads.add(t);
            t.start();
        }

        // Wait for all threads to finish and return the first index found
        for (Thread t : threads) {
            try {
                t.join();
            } catch (InterruptedException e) {
                return (int) Thread.currentThread().getId() * chunkSize;
            }
        }

        // Element not found
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int x = 7;
        int numThreads = 16;

        int idx = parallelLinearSearch(arr, x, numThreads);

        if (idx != -1) {
            System.out.println("Element found at index " + idx);
        } else {
            System.out.println("Element not found");
        }
    }
}

Compile and Run

If we save the above Java code in a file named , you can compile it using:

javac LinearSearch.java

To run the code, use:

java LinearSearch

This will perform Linear Search in 16 threads and give the output as:

Element found at index 6

With this article at OpenGenus, you must have the complete idea of how to do Linear Search in a multi-threaded way in Java Programming Language.