Multi-threaded C++ program for Linear Search

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:

1. Approach for Multi-threaded Linear Search
2. Multi-threaded C++ 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 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.