Overview

Linear search, in its basic form, identifies the position of a target element in a given array or list. When extended to find all occurrences, it retrieves every index where the target element appears. Given large arrays, this can be time-consuming. Therefore, utilizing the capabilities of modern multicore processors with multithreading can significantly expedite the search by examining multiple parts of the list concurrently.

Multithreading in Linear Search for All Occurrences

Using multithreading for searching all occurrences of an element introduces unique challenges. As multiple threads can find multiple occurrences simultaneously, we need a way to collect these indices efficiently.

1. Divide the Work: As before, split the array into smaller segments or "chunks." Each thread will have its distinct portion of the array to search through.
2. Concurrent Execution: Each thread will independently search its assigned chunk for the target element. Due to simultaneous searches, the overall search time often reduces for large arrays.
3. Collecting Results: Rather than a single shared variable, we'll use a shared collection (like a list) where threads can append indices of found occurrences. Synchronization mechanisms are essential to ensure thread-safe updates to this shared collection.

Step-by-step Algorithm

1. Make a list of numbers (let's call it arr) and decide on the number you want to find (let's call it key).
2. Make a shared list (let's call it found_places) where threads will add the places where the number shows up.
3. Start several threads, each one assigned to look through a specific part of the list.
4. When a thread finds the number, it adds the place to the found_places list.
5. Wait for all the threads to finish.
6. Check the found_places list:
   • If it’s empty, the number was not found.
   • If it has places in it, the number was found, and the list shows where.

Algorithm Walkthrough

Let’s imagine we have a list [4, 15, 12, 3, 12, 9, 12], and we want to find all the places of the number 12.

1. We decide to use 3 threads to speed things up. We also have a shared list (found_places) to store where we find 12. At first, it's empty.
2. We create a function FindAllPlaces for the threads to use:
   • a. The function knows which part of the list to check based on the thread's number.
   • b. It looks through its assigned numbers. If it finds 12, it adds the place to found_places.
3. We start our 3 threads. The first thread checks [4, 15], the second checks [12, 3], and the third checks [12, 9, 12].
4. The threads work at the same time. The second and third threads find 12.
5. They add the places of 12 (2, 4, and 6) to found_places. They use locks to make sure they don’t add to the list at the same time.
6. All threads are done. We check found_places and see 2, 4, 6. We print “Number found at places: 2, 4, 6”.
7. We’re done, and we found all places of 12 quicker by looking in three parts simultaneously.

Below are various implementations: