Overview

Linear search is a fundamental algorithm in computer science used to identify the position of a target element in a given array or list. It operates by examining each element sequentially until a match is found or the whole list has been searched. The search process can be time-consuming when the list is considerably large. Hence, leveraging the power of modern multicore processors using multithreading can expedite this search by allowing multiple parts of the list to be examined concurrently.

Multithreading in Linear Search

Multithreading involves executing multiple threads in parallel, making it an excellent tool for optimizing algorithms like linear search on multicore systems. Here's how we can apply multithreading to the linear search:

1. Divide the Work: Start by dividing the array into smaller segments or "chunks." The number of chunks typically matches the number of threads, ensuring that each thread has a distinct portion of the array to search through.
2. Concurrent Execution: Each thread independently searches its assigned chunk for the target element. Since these searches happen simultaneously, the total search time is often reduced, especially for large arrays.
3. Shared Variable for Result: As threads operate independently, there's a need for a shared or global variable where threads can update the result. This variable will store the index of the first occurrence of the target element found by any thread. We'll use synchronization mechanisms such as mutexes or locks to ensure that updates to this shared variable are thread-safe (i.e., not prone to concurrency issues).
4. Method of Division:
   • Block Division: Used in the C++ and Python implementations, the array is divided into contiguous blocks or chunks. If we have four threads, the first thread might handle indices 0-24, the second 25-49, and so on. Each thread looks only within its block.
   • Cyclic Division: Employed in the C# and Java implementations, it involves distributing array indices in a cyclic manner among threads. If we consider four threads, the first thread handles indices 0, 4, 8, etc., the second one manages indices 1, 5, 9, etc., and so forth. This method ensures that threads are less likely to congest or lock the same memory areas.

Step-by-step Algorithm

1. Initialize the list of numbers (arr) and the target number (key).
2. Set a shared variable (found_index) to -1 to indicate the target number is not found.
3. Start multiple threads, each assigned to search in a specific part of the list.
4. In each thread, search for the target number in the assigned part of the list.
   • If the target number is found, update found_index with the index of the number.
   • If the target number is already found by another thread then exit this thread
5. Wait for all threads to finish.
6. Check the value of found_index:
   • If it’s still -1, the target number was not found.
   • If it’s not -1, the target number was found, and found_index is its position in the list.

Algorithm Walkthrough

Now, let’s walk through the algorithm with an example:

1. Imagine we have a list of numbers: [4, 15, 7, 3, 12, 9], and we want to find the number 12.
2. We decide to use 2 threads to make the search faster. We also create a shared place (found_index) to store where we find the number, initially set to -1.
3. We create a function LinearSearch for the threads to run:
   • a. The function knows which part of the list to search based on the thread's number.
   • b. It looks through its assigned numbers. If it finds 12, it checks found_index.
   • c. If found_index is still -1, it updates it with the position of 12. If not, it means the other thread has already found it.
4. We start our 2 threads. One thread searches in the first half [4, 15, 7], and the other searches in the second half [3, 12, 9].
5. The threads run at the same time. The second thread finds 12 in its part of the list.
6. The second thread checks found_index, sees that it’s -1, updates it to 4 (the position of 12), and then finishes its job.
7. Both threads finish. We check found_index and see that it’s 4. We print “Number found at index: 4”.
8. The search is complete, and we did it faster by searching in two parts at the same time.