Parallel Binary Search Using Pthreads

binary-search-parallel-pthreads.c

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
 
#define ARRAY_SIZE 16  // Size of the array
#define NUM_THREADS 4  // Number of threads
#define TARGET 7       // Number to search for
 
int array[ARRAY_SIZE];
int found = -1;  // Index of the found element (-1 if not found)
 
// Struct for passing data to threads
typedef struct {
    int low;
    int high;
} SearchRange;
 
// Function executed by the thread
void *binary_search_thread(void *arg) {
    SearchRange *range = (SearchRange *)arg;
    int low = range->low;
    int high = range->high;
    int mid;
 
    while (low <= high && found == -1) {
        mid = low + (high - low) / 2;
        if (array[mid] == TARGET) {
            found = mid;  // Set the found index
            break;
        } else if (array[mid] < TARGET) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
 
    pthread_exit(NULL);
}
 
int main() {
    pthread_t threads[NUM_THREADS];
    SearchRange ranges[NUM_THREADS];
    int segment_size = ARRAY_SIZE / NUM_THREADS;
 
    // Initialize and sort the array
    for (int i = 0; i < ARRAY_SIZE; i++) {
        array[i] = i;  // Fill the array with sorted numbers
    }
 
    // Creating threads for binary search
    for (int i = 0; i < NUM_THREADS; i++) {
        ranges[i].low = i * segment_size;
        ranges[i].high = (i + 1) * segment_size - 1;
        pthread_create(&threads[i], NULL, binary_search_thread, &ranges[i]);
    }
 
    // Waiting for all threads to finish
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }
 
    // Check if the target was found
    if (found != -1) {
        printf("Target found at index: %d\n", found);
    } else {
        printf("Target not found\n");
    }
 
    return 0;
}

This program performs a parallel binary search using pthreads. Each thread conducts a binary search on a separate segment of the sorted array. The program divides the array into equal-sized segments and assigns each to a different thread.

Array Initialization: The array is initialized and sorted, as binary search works on sorted arrays.

Thread Function (binary_search_thread): Each thread performs binary search on its assigned segment. If the target is found, the thread updates the found index. The search in each segment is independent, and threads don't interfere with each other.

Main Function: Divides the array into segments and creates a thread for each segment. Each thread searches for the target in its segment. After all threads are done, the program checks if the target was found and prints the result.

Search Implementation: The binary search is performed within each segment. The search stops if a thread finds the target or after all threads have completed their search without finding the target.

This parallel binary search implementation can speed up the search process in large arrays, especially on multi-core systems, by dividing the search workload among multiple threads. Each thread independently searches a segment of the array, allowing for simultaneous searches in different parts of the array. This approach is effective for large data sets where traditional binary search may be less efficient due to the size of the data.