Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article at OpenGenus, we have explained how to do Linear Search in a multi-threaded way in C++ Programming Language. We have presented this with the complete C++ code.
Table of contents:
- Approach for Multi-threaded Linear Search
- Multi-threaded C++ program for Linear Search
- 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 C++:
- We use the thread library.
- We create a vector of threads.
vector<thread> threads;
- We create threads and run Linear Search on different chunks.
threads.emplace_back( /* ... */ );
for (auto& t : threads) {
t.join();
if (t.joinable()) {
// ...
}
}
- One can get the result from a thread as follows:
int index = t.join();
Most systems have more than 64 threads today. So, if there are M threads, the time complexity of Linear Search becomes O(N/M).
Multi-threaded C++ program for Linear Search
Following is the complete C++ program to do Linear Search in multi-threaded way:
// Part of iq.opengenus.org
#include <iostream>
#include <vector>
#include <thread>
using namespace std;
// Perform linear search in parallel
int linearSearchMultithreaded(vector<int>& arr, int x, int num_threads) {
int n = arr.size();
int chunk_size = n / num_threads;
vector<thread> threads;
// Create threads and search through different chunks of the array
for (int i = 0; i < num_threads; i++) {
threads.emplace_back([i, chunk_size, &arr, x]() {
int start = i * chunk_size;
int end = (i == num_threads - 1) ? n : (i + 1) * chunk_size;
for (int j = start; j < end; j++) {
if (arr[j] == x) {
return j;
}
}
return -1;
});
}
// Wait for all threads to finish and return the first index found
for (auto& t : threads) {
t.join();
if (t.joinable()) {
int index = t.join();
if (idx != -1) {
return index;
}
}
}
// Element not found
return -1;
}
int main() {
vector<int> arrayList = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int search_for = 7;
int num_threads = 4;
int index = linearSearchMultithreaded(arrayList, search_for, num_threads);
if (index != -1) {
cout << "Element found at index " << index << endl;
} else {
cout << "Element not found" << endl;
}
return 0;
}
Compile and Run
Save the above code in a file named as LinearSearch.cpp
Use the following command to compile the above code:
g++ -std=c++11 -pthread LinearSearch.cpp -o LinearSearch
The above command is using the option o to create an executable with name LinearSearch. Note we have enabled linking to the thread library using pthread option.
To run the executable, use the following command:
./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 C++ Programming Language.